text:
# What is the direction of dot product and cross product of vector A and B? [closed]

What is the direction of the dot product and the cross product of vectors A and B?

• No better, concise answer than what Red Act has provided! – Swami Sep 26 '14 at 6:09

## 4 Answers

The dot product of two vectors doesn't have a direction, because it's a scalar (single number), not a vector.

The cross product $A\times B$ is perpendicular to both $A$ and $B$. If on your right hand, your thumb is sticking up and pointing in the direction of $A$, and your index finger is pointing in the direction of $B$, then your palm is facing in the direction of $A\times B$

The result of a dot product is, as Red Act said, a scalar, it must not have a direction. The result of a cross product must be a vector. It must have a direction. Curl your right hand fingers - moving them from $A$ towards $B$ via the shorter angle, your thumb gives the direction of the result of the cross product.

As with the other answers by Swami and Red ACt, the scalar product has no direction, the vector product is orthogonal to the plane defined by the two vectors (and nought if the two vectors are colinear).

All this seems a bit arbitrary at first meeting: you're clearly a bit bewildered by this and this is quite normal. So, although the following is a bit further to your question's requirements, I think it may help: it would certainly have helped me when I first came across these ideas.

The scalar product is a scalar and is precisely the further information, other than the cross product itself, that you need to "invert" the cross product

The scalar and vector product together are working parts of a more intuitive whole: an invertible vector product. Suppose we have vectors $X, \,Y$, then the two products are the scalar $z=X\cdot Y$ and the vector $Z=X\times Y$. Now, suppose we know $z$, $Z$ and $X$: we can reconstruct from this information $Y$ as follows: we have the identity $X\times(X\times Y)=X\cdot Y X - |X|^2 Y$ so that

$$Y = \frac{1}{|X|^2}(z X - X\times Z)\tag{1}$$

i.e. we have retrieved $Y$, and we can do this as long as $X$ is nonzero so that $|X|^2\neq0$. The vector product $X\times Y$ is unchanged by the addition of any scalar multiple of $Y$ to $X$, i.e. $X\times Y = (X + \alpha\,Y)\times Y$. So, once again, we see why:

The scalar product is a scalar and is precisely the further information you need to "invert" the cross product

This futher information is $\alpha$ in the expression $X\times Y = (X + \alpha\,Y)\times Y$, which the vector product annihilates. So the scalar product's $X \cdot Y$ role is to fetch the component of $X$ in the direction of $Y$, i.e. the part annihilated by the vector product. If instead of 3 dimensional vectors, we think about four dimensional entities of the form $\chi = (x,\,X)$ where $x$ is a scalar and $X$ a three dimensional vector, we can define a new, generalised product on these entities using the scalar and vector product:

$$(x,\,X) \, (y,\,Y) \stackrel{def}{=} (x\,y - X\cdot Y,\,x\,Y + y\,X + X\times Y)$$

then, with a bit of fiddling, you can show that the inverse of the entity $(x,\,X)$ is indeed:

$$(x,\,X)^{-1} = \frac{1}{x^2+|X|^2}\,(x,\,-X)\tag{3}$$

and so the inverse exists and is unique as long as the "length" $x^2 + |X|^2$ of the entity $(x,\,X)$ is not nought. What you've now defined is in fact the skew field of quaternions and historically these were the first entities to be used for 3D spatial vector analysis before Oliver Heaviside and Josiah Gibbs "pruned" them back to the separate scalar and vector product. Sometimes calculations are easier with quaternions (I certainly find the angular momentum of a falling cat easier to think about, as in my article here) or, more generally in Clifford Algebras, but it sounds as though it might be some time before you meet those. The case of "inverting the scalar and vector product" given in (1) is a special case of (2) and (3) when there are no scalar parts to the entities, i.e. when we deal with "pure vectors" (a.k.a. pure imaginary quaternions) of the form $(0,\,X)$ and $(0,\,Y)$.

To complete the given answers you have to keep in mind that the number of the cross product is the multiplication of the numbers of thus vectors and the sinus of the angle between them. If the angle is zero than there does not exist a direction of the cross product.


text:
Constructions | NCERT Class 9 Maths

Go back to  'NCERT Solution for Class 9th Maths'

This chapter focuses on introduction and basic constructions like bisecting the angle, perpendicular bisector of the given line, angle of 60 with the given line and followed by constructions of triangle which include constructing a triangle given its base, a base angle and sum of other two sides, constructing a triangle given its base, a base angle and the difference of the other two sides and also constructing a triangle, given its perimeter and its two base angles. All the constructions are explained with different figures and diagrams.

format: plain


text:
# Python problems on Lion (mostly self-inflicted)

The upgrade of my MacBook Air to Lion went gone pretty smoothly, but I had problems with Python,1 some of which were my fault, some of which were Apple’s.

Unsurprisingly, the default version of Python on Lion is from the 2.7 branch:

$python --version Python 2.7.1  You can, if you wish, run earlier versions instead: $ python2.6 --version
Python 2.6.6
$python2.5 --version Python 2.5.5  Versions earlier than 2.5 aren’t available. The versions available in Snow Leopard were 2.6.1 and 2.5.4. The first Python program I tried to run was Dr. Twoot. Dr. Twoot itself is written in JavaScript, but since Twitter changed from basic authentication to OAuth, I’ve had Dr. Twoot communicate with the Twitter server via a CGI script (written in Python) running under the Apache server that comes with OS X. Dr. Twoot failed for what turned out to be a variety of reasons. First, Apache wasn’t running, so I guess the Lion updater didn’t maintain the Web Sharing setting. Dr. Twoot continued to fail after I turned Web Sharing on, apparently because of some setting in Lion’s /etc/apache/httpd.conf file. I couldn’t access anything under the DocumentRoot, including the necessary CGI script. Fortunately, the Lion updater had preserved my old http.conf under a different name, and when I changed the names and restarted Apache, I was able to access the DocumentRoot again. But that didn’t mean Dr. Twoot was working. The CGI script was throwing an error, which was a Python problem. The error was a missing third-party library, oauth2. This error made sense to me: 1. The CGI script is run by the default Python, /usr/bin/python. 2. The default Python is version 2.7. 3. Version 2.7 looks for third-party libraries in /Library/Python/2.7/site-packages. 4. The outh2 library can’t be in the 2.7 site-packages directory because I installed it when Python 2.6 was the default. The long-term solution would be to install oauth2—and all the other third-party libraries I use—in /Library/Python/2.7/site-packages, but I wanted to get Dr. Twoot up and running quickly, so I changed the shebang line of the CGI script from #!/usr/bin/python  to #!/usr/bin/python2.6  because I knew I had oauth2 installed the 2.6 site-packages directory. When that failed, and the error message still said the oauth2 library couldn’t be found, I navigated to /Library/Python/2.6/site-packages to see what was wrong. Here’s what I found: $ ls
README

There were no libraries in /Library/Python/2.6/site-packages, just a worthless README. Which means that the Lion updater had overwritten my entire /Library/Python/2.6/site-packages directory.

I’m pretty sure this isn’t kosher. The whole point of a site-packages directory is to keep system updates and third-party libraries separated and unaffected by each other. I checked my office computer, which is still running Snow Leopard. It has libraries in both /Library/Python/2.5/site-packages and /Library/Python/2.6/site-packages. The former were installed under Leopard (when the default Python was version 2.5) and the latter were installed under Snow Leopard; the Snow Leopard update didn’t blow away all libraries installed under Leopard. Lion, unfortunately, wasn’t as well-behaved.

So I set about installing the missing libraries. At first, easy_install failed with every library I tried. Eventually, I realized that I was using a mismatched version of easy_install in /usr/local/bin instead of the Lion-supplied one in /usr/bin. I don’t know why there was an easy_install in /usr/local/bin, but after getting rid of it, the troubles went away.

Until I tried to install appscript. The appscript library, which I use in several scripts to do AppleScript-like things in Python, requires the compilation of some C source. The compilation failed with all sorts of nasty error messages referring to llvm-gcc-4.2. I knew that Apple had switched from the old gcc compiler, and wondered whether that was the problem.

Several Python libraries won’t compile with llvm-gcc-4.2. Is there a way to force easy_install/setuptools to use plain ol’ gcc?

7:44 PM Sun Jul 24, 2011

Almost as soon as I tweeted this, I realized what the problem was: I’d forgotten to update Xcode after updating to Lion. As I began the download of Xcode from the Mac App Store, I got this confirmation from @mr_lightwolf:

@drdrang If you didn’t reinstall Xcode after upgrading Lion, tons of stuff will break.

8:22 PM Sun Jul 24, 2011

Xcode 4.1 took over an hour to download and install, but when it was done easy_install worked perfectly for all my libraries.

To summarize, if you haven’t updated to Lion yet, and you want to avoid the problems I had, be sure to

1. Make a list of all the third-party libraries you currently have installed under Python 2.6, because you’ll have to reinstall all of them for 2.7 and you won’t have the 2.6 site-packages directory to refer to.
2. Update to Lion.
3. Update to Xcode 4.1. It’s free in the App Store.
4. Make sure the easy_install you use is the one in /usr/bin.

On the non-Python front, if you run a local web server, you might want to put a copy of all your Apache configuration files into your home directory (or Dropbox) before updating to Lion. My configuration files were preserved by the updater, but a belt-and-suspenders approach is safer.

I suppose I’ll go ahead and install Python 3.2 in the next few weeks. None of my workaday scripts use it, but now that it’s 2½ years and 2 point releases old, it’s probably time to get with the program.

1. Problems with Pythons would be a good title for a Gilderoy Lockhart book.

## 10 Responses to “Python problems on Lion (mostly self-inflicted)”

1. A few notes and things that I have learnt, often painfully:

• Use virtualenv to manage packages as much as possible. It helps keep things clean in general. And since it stores libraries in ~/.virtualenv/ you’d be safe through an upgrade (personally, I installed Lion from scratch)

• Use pip instead of easy_install. You can get a printout of all the packages installed, save them to a file, and install everything from that file next time you set up a virtualenv.

• Consider homebrew which will install its stuff in /usr/local/ and shouldn’t be touched by the OS for any reason. I use Python from homebrew because of some local patching I need to do. Homebrew has Python 3.x as well and it should make installing it easier.

• Submit a bug report to Apple. I agree that this is a pretty big issue, and I reckon I’d be pissed if I lost a bunch of stuff from site-packages the way you did. This has a lot to do with the install path for these packages, which is why I prefer the homebrew approach of /usr/local/ (which, as the project states, is something Apple says they don’t touch, and never put anything into themselves)

2. speno says:

Another vote for homebrew. Then you can worry about virtualenv and pip etc. You really don’t want to install Python modules anywhere that your vendor controls and is likely to mess with. Homebrew installs everything in /usr/local.

3. Been meaning to look into pip; inertia’s been keeping me with easy_install.

How does virtualenv compare with pythonbrew?

As for Hombrew, I know everyone says it’s great, but people said the same thing about Fink and Mac/DarwinPorts, and both of those turned into dependency nightmares. I’m still leery and prefer to install extras “by hand” in /usr/local.

4. speno says:

I saw pythonbrew but wasn’t interested in it so I can’t speak on it.

Homebrew just automates the way you already want to work. It compiles stuff for you and sticks it in /usr/local. It’s the first package system that does that, or the first one that I actually like. You still get that “by hand” feel except it’s not “by hand” anymore. :-)

My biggest gripe with easy_install was .egg files. I don’t want .egg files. I know tricks to make it install in non .egg format but pip just does that by default.

5. Clark says:

Have you been able to compile the full appscript with Lion? I don’t mean what gets compiled with easy_install but the actual appscript project. I futzed around with it for several hours this week but never made a whole lot of progress - probably due to ignorance on my part of Xcode 4. It was pretty frustrating as I was hoping to test out some obj-C appscript stuff.

6. Clark,
No, I just did the Python library. No particular interest in ObjC programming at this stage.

7. Curses. Things breaking without an Xcode reinstall explains why I never could get any Octave packages to install/compile last week. But I don’t think I have enough hard drive space to reinstall Xcode at the moment. Something I’ve been meaning to do something about, but haven’t had time yet.

Like I said: Curses.

8. Shayne says:

I still have no damn idea where Apple is putting my django files so I can point eclipse at it. Its really really productivity killing and annoying. I just dont get why apple cant leave that stuff alone. Not broken, not for fixing, etc. :(

9. philotas says:

If I haven’t upgraded to Lion already, couldn’t I just copy the /Library/Python/2.6/site-packages from SL to /Library/Python/2.7/site-packages on Lion (given that they are compatible with 2.7)?

10. You can do that, philotas, but you should copy the 2.6/site-packages contents to a safe place before upgrading to Lion. Recall that my 2.6/site-packages got wiped out by the upgrade.

I still think the 4-step process outlined near the end of the post is the best approach. It’ll give you the appropriate modules for 2.7.


text:
# mdframed environment not breaking over pages

I apologise in advance because I cannot provide an MWE.

I am writing a book with a custom (Springer) format and I wish to use mdframed to provide an example environment. I adapted an example from the documentation and came up with this as a first draft:

\documentclass{article}
\usepackage{mdframed}
\usepackage{tikz}
\usepackage{blindtext}

\newcounter{exampl}[section]
\newenvironment{exampl}[1][]{%
\stepcounter{exampl}%
\ifstrempty{#1}%
{\mdfsetup{%
frametitle={%
\tikz[baseline=(current bounding box.east),outer sep=0pt]
\node[anchor=east,rectangle,fill=black!10]
{\strut Example~\thesection .\theexampl};},nobreak=false}
}%
{\mdfsetup{%
frametitle={%
\tikz[baseline=(current bounding box.east),outer sep=0pt]
\node[anchor=east,rectangle,fill=black!10]
{\strut Example~\thesection .\theexampl:~#1};},nobreak=false}%
}%
\mdfsetup{innertopmargin=10pt,linecolor=black!10,nobreak=false,%
linewidth=2pt,topline=true,backgroundcolor=black!05,%
frametitleaboveskip=\dimexpr-\ht\strutbox\relax}
\begin{mdframed}[]\relax%
}{\end{mdframed}}

\begin{document}

\section{Introduction}

\blindtext

\blindtext

\blindtext

\begin{exampl}[Lorem ipsum]
\blindtext

\begin{tabular}{cc}
A & Table\\
\end{tabular}

\Blindtext
\end{exampl}

\end{document}

In the MWE provided, the exampl works fine and uses appropriate page-breaks. However, in the context of the source of the book I'm working on, the same environment will not break.

As per the MWE above, I tried explicitly adding nobreak=false everywhere to try force the page-break, but to to avail.

I've tried debugging it and working back towards an MWE, but to no avail. I believe it might be something in the custom book template that's causing the problem.

I know that my problem might not be reproducible and thus is not ideal for this site, but I was hoping someone might be able to offer some common reasons as to why an mdframed environment won't break across pages. I'm hoping for clues to debug the problem.

What are common reasons why page-breaking might stop working in mdframed?

Any tricks to try force page-breaking again?

• Use the framed package, it breaks across the pages. – skpblack Aug 1 '14 at 19:59
• Yep, but in theory, mdframed should also break across pages. – badroit Aug 1 '14 at 20:03

Ah okay, only a few minutes after asking the question, I found the answer (creating the MWE helped).

The problem was with the picins package loaded (I think) in the template class. If you load picins, the mdframed environments will no longer break over pages, as per this M(N)WE:

\documentclass{article}
\usepackage{picins}
\usepackage{mdframed}
\usepackage{tikz}
\usepackage{blindtext}

\newcounter{exampl}[section]
\newenvironment{exampl}[1][]{%
\stepcounter{exampl}%
\ifstrempty{#1}%
{\mdfsetup{%
frametitle={%
\tikz[baseline=(current bounding box.east),outer sep=0pt]
\node[anchor=east,rectangle,fill=black!10]
{\strut Example~\thesection .\theexampl};},nobreak=false}
}%
{\mdfsetup{%
frametitle={%
\tikz[baseline=(current bounding box.east),outer sep=0pt]
\node[anchor=east,rectangle,fill=black!10]
{\strut Example~\thesection .\theexampl:~#1};},nobreak=false}%
}%
\mdfsetup{innertopmargin=10pt,linecolor=black!10,nobreak=false,%
linewidth=2pt,topline=true,backgroundcolor=black!05,%
frametitleaboveskip=\dimexpr-\ht\strutbox\relax}
\begin{mdframed}[]\relax%
}{\end{mdframed}}

\begin{document}

\section{Introduction}

\blindtext

\blindtext

\blindtext

\begin{exampl}[Lorem ipsum]
\blindtext

\begin{tabular}{cc}
A & Table\\
\end{tabular}

\Blindtext
\end{exampl}

\end{document}

The order of loading the packages doesn't seem to matter either, so either choose page-breaking in mdframed or picins I guess.

Anyways, sorry for the noise but maybe this will help someone who encounters a similar issue later.


text:
# Page:Grundgleichungen (Minkowski).djvu/38

 (66) ${\displaystyle \left|{\frac {\partial L}{\partial x_{1}}},\ {\frac {\partial L}{\partial x_{2}}},\ {\frac {\partial L}{\partial x_{3}}},\ {\frac {\partial L}{\partial x_{4}}}\right|}$

If ${\displaystyle s=\left|s_{1},\ s_{2},\ s_{3},\ s_{4}\right|}$ is a space-time vector of the 1st kind, then

 (67) ${\displaystyle lor\ {\bar {s}}={\frac {\partial s_{1}}{\partial x_{1}}}+{\frac {\partial s_{2}}{\partial x_{2}}}+{\frac {\partial s_{3}}{\partial x_{3}}}+{\frac {\partial s_{4}}{\partial x_{4}}}}$

In case of a Lorentz transformation ${\displaystyle {\mathsf {A}}}$, we have

${\displaystyle lor'\ {\bar {s}}'=(lor\ {\mathsf {A}})({\mathsf {\bar {A}}}{\bar {s}})=lor\ {\bar {s}}}$,

i.e., lor s is an invariant in a {sc|Lorentz}}-transformation.

In all these operations the operator lor plays the part of a space-time vector of the first kind.

If f represents a space-time vector of the second kind, -lor f denotes a space-time vector of the first kind with the components

${\displaystyle {\begin{array}{ccccccc}&&{\frac {\partial f_{12}}{\partial x_{2}}}&+&{\frac {\partial f_{13}}{\partial x_{3}}}&+&{\frac {\partial f_{14}}{\partial x_{4}}},\\\\{\frac {\partial f_{21}}{\partial x_{1}}}&&&+&{\frac {\partial _{23}}{\partial x_{3}}}&+&{\frac {\partial _{24}}{\partial x_{4}}},\\\\{\frac {\partial f_{31}}{\partial x_{1}}}&+&{\frac {\partial _{32}}{\partial x_{2}}}&&&+&{\frac {\partial _{34}}{\partial x_{4}}},\\\\{\frac {\partial f_{41}}{\partial x_{1}}}&+&{\frac {\partial _{42}}{\partial x_{2}}}&+&{\frac {\partial _{43}}{\partial x_{3}}},\end{array}}}$

So the system o£ differential equations (A) can be expressed in the concise form

 {A} ${\displaystyle lor\ f=-s}$

and the system (B) can be expressed in the form

 {B} ${\displaystyle lor\ F^{*}=0}$

Referring back to the definition (67) for ${\displaystyle lor\ {\bar {s}}}$, we find that the combinations ${\displaystyle lor({\overline {lor\ f}})}$ and ${\displaystyle lor({\overline {lor\ F^{*}}})}$ vanish identically, when f and F* are alternating matrices. Accordingly it follows out of (A), that

 (68) ${\displaystyle {\frac {\partial s_{1}}{\partial x_{1}}}+{\frac {\partial s_{2}}{\partial x_{2}}}+{\frac {\partial s_{3}}{\partial x_{3}}}+{\frac {\partial s_{4}}{\partial x_{4}}}=0}$,


text:
# Personnel selection. Suppose that 6 female and 5 male applicants have been successfully screened for 5 positions. If the 5 positions are filled at random from the 11 finalists, what is the probability of selecting (A) 3 females and 2 males? (B) 4 females and 1 male? (C) 5 females?

Personnel selection. Suppose that 6 female and 5 male applicants have been successfully screened for 5 positions. If the 5 positions are filled at random from the 11 finalists, what is the probability of selecting
(A) 3 females and 2 males?
(B) 4 females and 1 male?
(C) 5 females?
You can still ask an expert for help

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

un4t5o4v
Data analysis
Note : As per authoring guidelines, when multiple subparts are posted, then only first three subparts are to be answered.
Given there is selection for a Personnel.
And there are 11 finalists in which 6 are female and 5 are female.
And there are only 5 posts vacant.
To find the probability of selecting as below.
Total ways
Total number of ways of selecting 5 people from 11 finalists is given by,
$11P5$

$=55.440$
Probability is given by the ratio of number of favourable ways to the total number of ways.
Note :

A) 3 females and 2 males
3 females selected from 6 female finalists in $6P3$ ways

$=120$
2 males selected from 5 male finalists in $5P2$ ways

$=20$
Favourable ways
Probability $=2400/55.440$
$=0.0432900433$
Hence probability of selecting 3 females and 2 males is 0.04329
(Rounded to 5 decimals)
B) 4 females and 1 males
4 females selected from 6 female finalists in $6P4$ ways

$=360$
1 male selected from 5 male finalists in $5P1$ ways
$=5$
Favourable ways
Probability $=1800/55.440$
$=0.0324675325$
Hence probability of selecting 4 females and 1 male is 0.0324675
(Rounded to 7 decimals)
C) 5 females
5 females selected from 6 female finalists in $6P5$ ways

$=720$
Favourable ways = 720
Probability $=720/55.440$
$=0.012987013$
Hence probability of selecting 5 females is 0.012987
(Rounded to 6 decimals)


text:
Defective colouring of graphs excluding a subgraph or minor

# Defective colouring of graphs excluding a subgraph or minor

Patrice Ossona de Mendez Patrice Ossona de Mendez
Centre d’Analyse et de Mathématiques Sociales (CNRS, UMR 8557)
190-198 avenue de France, 75013 Paris, France
— and —
Computer Science Institute of Charles University (IUUK)
Malostranské nám.25, 11800 Praha 1, Czech Republic
Sang-il Oum Sang-il Oum
Department of Mathematical Sciences, KAIST
Daejeon, South Korea
and  David R. Wood David R. Wood
School of Mathematical Sciences, Monash University
Melbourne, Australia
July 6, 2019
###### Abstract.

Archdeacon (1987) proved that graphs embeddable on a fixed surface can be -coloured so that each colour class induces a subgraph of bounded maximum degree. Edwards, Kang, Kim, Oum and Seymour (2015) proved that graphs with no -minor can be -coloured so that each colour class induces a subgraph of bounded maximum degree. We prove a common generalisation of these theorems with a weaker assumption about excluded subgraphs. This result leads to new defective colouring results for several graph classes, including graphs with linear crossing number, graphs with given thickness (with relevance to the earth–moon problem), graphs with given stack- or queue-number, linklessly or knotlessly embeddable graphs, graphs with given Colin de Verdière parameter, and graphs excluding a complete bipartite graph as a topological minor.

Ossona de Mendez is supported by grant ERCCZ LL-1201 and by the European Associated Laboratory “Structures in Combinatorics” (LEA STRUCO), and partially supported by ANR project Stint under reference ANR-13-BS02-0007. Research of Wood is supported by the Australian Research Council.

## 1. Introduction

A graph is -colourable with defect , or -improper -colourable, or simply -colourable, if each vertex of can be assigned one of colours so that at most neighbours of are assigned the same colour as . That is, each monochromatic subgraph has maximum degree at most . Obviously the case corresponds to the usual notion of graph colouring. Cowen et al. [26] introduced the notion of defective graph colouring, and now many results for various graph classes are known. This paper presents -colourability results for graph classes defined by an excluded subgraph, subdivision or minor. Our primary focus is on minimising the number of colours rather than the degree bound . This viewpoint motivates the following definition. The defective chromatic number of a graph class is the minimum integer (if such a exists) for which there exists an integer such that every graph in is -colourable.

Consider the following two examples: Archdeacon [4] proved that for every surface , the defective chromatic number of graphs embeddable in equals 3. And Edwards, Kang, Kim, Oum, and Seymour [32] proved that the class of graphs containing no minor has defective chromatic number (which is a weakening of Hadwiger’s conjecture). This paper proves a general theorem that implies both these results as special cases. Indeed, our theorem only assumes an excluded subgraph, which enables it to be applied in more general settings.

For integers , let be the bipartite graph obtained from by adding new vertices, each adjacent to a distinct pair of vertices in the colour class of vertices in (see Figure 1). Our main result shows that every graph excluding as a subgraph is -colourable, where depends on , and certain density parameters, which we now introduce.

For a graph , the most natural density parameter to consider is the maximum average degree, denoted , which is the maximum of the average degrees of all subgraphs of ; that is,

Closely related to maximum average degree is degeneracy. A graph is -degenerate if every subgraph of has a vertex of degree at most . Every graph is -degenerate. It follows that the chromatic number (and even the choice number) of a graph is at most . Bounds on defective colourings have also been obtained in terms of maximum average degree. In particular, Havet and Sereni [38] proved that every graph with is -colourable, and that there exist non--colourable graphs whose maximum average degree tends to when goes to infinity, which shows the limit of the maximum average degree approach for defective colouring (see also [29, 10, 13, 52, 20, 15, 14, 24]).

In addition to maximum average degree we consider the density of shallow topological minors (see [66] for more on this topic). A graph is a minor of a graph if a graph isomorphic to can be obtained from a subgraph of by contracting edges. A graph is a topological minor of a graph if a subdivision of is a subgraph of . A -subdivision of a graph is a graph obtained from by subdividing each edge at most times, or equivalently replacing each edge by a path of length at most . The exact -subdivision of is the graph obtained from by subdividing each edge exactly once. For a half integer (that is, a number such that is an integer), a graph is a depth- topological minor of a graph if a -subdivision of is a subgraph of . For a graph , let be the set of all depth- topological minors of . The topological greatest reduced average density (or top-grad) with rank of a graph is defined as

 ˜∇r(G):=maxH∈G˜▽r|E(H)||V(H)|.

Note that .

The following is our main result (see Theorem 2.3 for a more precise version).

###### Theorem 1.1.

Every graph with no subgraph has an -colouring, where depends on , , and

We actually prove this result in the setting of defective list colourings, introduced by Eaton and Hull [31] and since studied by several authors [17, 18, 19, 38, 61, 81, 87, 89, 94, 92, 93]. A -list assignment of a graph is a function that assigns a set of exactly colours to each vertex . Then an -colouring of is a function that assigns a colour in to each vertex . If an -colouring has the property that every vertex has at most neighbours having the same colour as , then we call it an -colouring with defect , or -defective. A graph is -choosable with defect , or -improper -choosable, or simply -choosable if for every -list assignment of , there exists a -defective -colouring of . For example, the result of Havet and Sereni [38] mentioned above applies in the setting of -choosability. The defective choice number of a graph class is the minimum integer (if such a exists) for which there exists an integer such that every graph in is -choosable.

The paper is organised as follows. Section 2 presents the proof of our main result (a choosability version of Theorem 1.1). The subsequent sections present several applications of this main result. In particular, Section 3 gives results for graphs with no 4-cycle, and other graph classes defined by an excluded subgraph. Section 4 presents defective 3-colourability results for graphs drawn on surfaces, even allowing for a linear number of crossings, thus generalising the result of Archdeacon mentioned above. Section 5 gives bounds on the defective chromatic number and defective choice number of graphs with given thickness, and of graphs with given stack- or queue-number. One result here is relevant to the earth–moon problem, which asks for the chromatic number of graphs with thickness 2. While it is open whether such graphs are 11-colourable, we prove they are 11-colourable with defect 2. Section 6 studies the defective chromatic number of minor-closed classes. We determine the defective chromatic number and defective choice number of linklessly embeddable graphs, knotlessly embeddable graphs, and graphs with given Colin de Verdière parameter. We then prove a strengthening of the result of Edwards et al. [32] mentioned above. Finally, we formulate a conjecture about the defective chromatic number of -minor-free graphs, and prove several special cases of it.

## 2. Main Proof

An edge in a graph is -light if both endpoints of have degree at most . There is a large literature on light edges in graphs; see [11, 49, 50, 47, 16, 9] for example. Many of our results rely on the following sufficient condition for -choosability. Its proof is essentially identical to the proof of a lemma by Lih et al. [61, Lemma 1]. Škrekovski [81] proved a similar result with .

###### Lemma 2.1.

For integers , if every subgraph of a graph has a vertex of degree at most or an -light edge, then is -choosable.

###### Proof.

Let be a -list assignment for . We prove by induction on that every subgraph of is -colourable with defect . The base case with is trivial. Consider a subgraph of . If has a vertex of degree at most , then by induction is -colourable with defect , and there is a colour in used by no neighbour of which can be assigned to . Now assume that has minimum degree at least . By assumption, contains an -light edge . By induction, has an -colouring with defect . If , then is also an -colouring of with defect . Now assume that . We may further assume that is not an -colouring of with defect . Without loss of generality, has exactly neighbours (including ) coloured by . Since , there are at most neighbours not coloured by . Since contains colours different from , there is a colour used by no neighbour of which can be assigned to . ∎

To state our main result, we use the following auxiliary function. For positive integers , and positive reals and , let

 N1(s,t,δ,δ1):=⎧⎪ ⎪ ⎪⎨⎪ ⎪ ⎪⎩(δ−s)((⌊δ1⌋s−1)(t−1)+12δ1)+δif s>2,12(δ−2)δ1t+δif s=2,t−1if s=1.
###### Lemma 2.2.

For positive integers , , and positive reals , , let . If every subgraph of a graph has average degree at most and every graph whose exact -subdivision is a subgraph of has average degree at most , then at least one of the following holds:

1. contains a subgraph,

2. has a vertex of degree at most ,

3. has an -light edge.

###### Proof.

The case is simple: If (i) does not hold, then , in which case either has no edges and (ii) holds, or has an edge and (iii) holds since . Now assume that .

Assume for contradiction that has no subgraph, that every vertex of has degree at least (thus ), and that contains no -light edge.

Let be the set of vertices in of degree at most . Let . Let and . Since has a vertex of degree at most and , we deduce that . Note that no two vertices in are adjacent.

Since the average degree of is at most ,

 (ℓ+1)b+sa⩽2|E(G)|⩽δ(a+b).

That is,

 (1) (ℓ+1−δ)b⩽(δ−s)a.

Let be a minor of obtained from by greedily finding a vertex having a pair of non-adjacent neighbours , in and replacing by an edge joining and (by deleting all edges incident with except , and contracting ), until no such vertex exists.

Let and . Clearly the exact -subdivision of is a subgraph of . So every subgraph of has average degree at most . Since contains at least edges,

 (2) a−a′⩽12δ1b.

A clique in a graph is a set of pairwise adjacent vertices. Let be the number of cliques of size in . Since is -degenerate,

 M⩽(⌊δ1⌋s−1)b

(see [66, p. 25] or [88]). If , then the following better inequality holds:

 M⩽12δ1b.

For each vertex , since was not contracted in the creation of , the set of neighbours of in is a clique of size at least . Thus if , then there are at least vertices in sharing at least common neighbours in . These vertices and their common neighbours in with the vertices in form a subgraph of , contradicting our assumption. Thus,

 (3) a′⩽M(t−1).

By (1), (2) and (3),

 ℓ+1⩽(δ−s)(Mb(t−1)+12δ1)+δ,

contradicting the definition of . ∎

Lemmas 2.2 and 2.1 imply our main result:

###### Theorem 2.3.

For integers , every graph with no subgraph is -choosable, where .

###### Proof.

By definition, every subgraph of has average degree at most and every graph whose exact -subdivision is a subgraph of has average degree at most . By Lemma 2.2, every subgraph of has a vertex of degree at most or has an -light edge, where . By Lemma 2.1 with , we have that is -choosable. ∎

The following recursive construction was used by Edwards et al. [32] to show that their theorem mentioned above is tight. We use this example repeatedly, so include the proof for completeness. If , then let . If , then let be obtained from the disjoint union of copies of by adding one new vertex adjacent to all other vertices. Note that Havet and Sereni [38] used a similar construction to prove their lower bound mentioned above.

###### Lemma 2.4 (Edwards et al. [32]).

For integers and , the graph has no minor and no -colouring.

###### Proof.

We proceed by induction on . In the base case, , and every 1-colouring has a colour class (the whole graph) inducing a subgraph with maximum degree larger than . Thus is not -colourable. Now assume that and the claim holds for . Let be the dominant vertex in . Let be the components of , where each is isomorphic to .

If contains a minor, then some component of contains a minor, which contradicts our inductive assumption. Thus contains no minor.

Suppose that is an -colouring of . We may assume that . If has a vertex of colour for each , then has more than neighbours of colour , which is not possible. Thus some component has no vertex coloured , and at most colours are used on . This contradicts the assumption that has no -colouring. ∎

Of course, for integers , the graph has no minor, no topological minor, and no -minor. Thus Lemma 2.4 shows that the number of colours in Theorem 2.3 is best possible. In other words, Theorem 2.3 states that defective chromatic number and defective choice number of every class of graphs of bounded with no subgraph are at most , and Lemma 2.4 shows that the number of colours cannot be decreased.

## 3. Excluded Subgraphs

This section presents several applications of our main result, in the setting of graph classes defined by an excluded subgraph. Since contains and a -subdivision of , Theorem 2.3 immediately implies:

• Every graph with no subgraph is -choosable, where depends on , , and .

• Every graph with no subgraph isomorphic to a -subdivision of is -choosable, where depends on , and .

### 3.1. No 4-Cycles

Since is the -cycle, Theorem 2.3 with and implies the following.

###### Corollary 3.1.

Every graph with no -cycle is -choosable, where .

###### Corollary 3.2.

Every graph with no minor nor -cycle subgraph is -choosable.

For planar graphs, . Indeed for planar graphs with at least three vertices. creftype 3.1 says that every planar graph with no -cycle is -choosable. However, better degree bounds are known. Borodin et al. [12] proved that every planar graph with no cycle of length has a vertex of degree at most or a -light edge. By Lemma 2.1, planar graphs with no -cycle are -choosable. Note that planar graphs with no -cycle are also known to be -choosable [87].

### 3.2. Edge Partitions

He et al. [39] proved the following theorem on partitioning a graph into edge-disjoint subgraphs.

###### Theorem 3.3 (He et al. [39, Theorem 3.1]).

If every subgraph of a graph has a vertex of degree at most or an -light edge, then has an edge-partition into two subgraphs and such that is a forest and is a graph with maximum degree at most .

This theorem and Lemma 2.2 imply the following.

###### Theorem 3.4.

For an integer , every graph with no subgraph has an edge-partition into two subgraphs and such that is a forest and has maximum degree at most .

### 3.3. Nowhere Dense Classes

A class of graphs is nowhere dense [64] if, for every integer there is some such that no -subdivision of is a subgraph of a graph in . Nowhere dense classes are also characterised [65] by the property that for every integer there exists a function with such that every graph of order in the class has . In other words, for each integer every graph in the class has .

For nowhere dense classes, there is no hope to find an improper colouring with a bounded number of colours, since the chromatic number of a nowhere dense class is typically unbounded (as witnessed by the class of graphs such that ). However, by the above characterisation, Theorem 2.3 implies there is a partition of the vertex set into a bounded number of parts, each with ‘small’ maximum degree.

###### Corollary 3.5.

Let be a nowhere dense class. Then there exist and a function with such that every -vertex graph in is -choosable.

## 4. 3-Colouring Graphs on Surfaces

This section considers defective colourings of graphs drawn on a surface, possibly with crossings. First consider the case of no crossings. For example, Cowen et al. [26] proved that every planar graph is -colourable, improved to -choosable by Eaton and Hull [31]. Since is planar, by Lemma 2.4 the class of planar graphs has defective chromatic-number and defective choice number equal to 3. More generally, Archdeacon [4] proved the conjecture of Cowen et al. [26] that for every fixed surface , the class of graphs embeddable in has defective chromatic-number 3. Woodall [90] proved that such graphs have defective choice number 3. It follows from Euler’s formula that is not embeddable on for some constant (see Lemma 4.3), and that graphs embeddable in have bounded average degree and . Thus Theorem 2.3 implies Woodall’s result. The lower bound follows from Lemma 2.4 since is planar.

###### Theorem 4.1 ([4, 90]).

For every surface , the class of graphs embeddable in has defective chromatic-number 3 and defective choice number 3.

While our main goal is to bound the number of colours in a defective colouring, we now estimate the degree bound using our method for a graph embeddable in a surface of Euler genus . The Euler genus of an orientable surface with handles is . The Euler genus of a non-orientable surface with cross-caps is . The Euler genus of a graph is the minimum Euler genus of a surface in which embeds. For , define

 dg:=max{3,14(5+√24g+1)}.

The next two lemmas are well known. We include their proofs for completeness.

###### Lemma 4.2.

Every -vertex graph embeddable in a surface of Euler genus has at most edges.

###### Proof.

Suppose that , where . We may assume that . By Euler’s Formula, , implying . Since we have . Since ,

 3g−6>(d−3)n⩾(d−3)(2d+1)=2d2−5d−3.

Thus . By the quadratic formula, , which is a contradiction. Hence . ∎

###### Lemma 4.3 (Ringel [74]).

For every surface of Euler genus , the complete bipartite graph does not embed in .

###### Proof.

By Euler’s formula, every triangle-free graph with vertices that embeds in has at most edges. The result follows. ∎

Theorems 2.3, 4.3 and 4.2 imply that graphs embeddable in are -choosable. This degree bound is weaker than the bound of obtained by Archdeacon. However, our bound is easily improved. Results by Jendrol and Tuhársky [48] and Ivančo [44] show that every graph with Euler genus has a -light edge. Then Lemma 2.1 directly implies that every graph with Euler genus is -choosable. Still this bound is weaker than the subsequent improvements to Archdeacon’s result of -colourability by Cowen et al. [25] and to -choosability by Woodall [90]; also see [19].

### 4.1. Linear Crossing Number

We now generalise Theorem 4.1 to the setting of graphs with linear crossing number. For an integer and real number , say a graph is -close to Euler genus (resp. -close to planar) if every subgraph of has a drawing on a surface of Euler genus (resp. on the plane) with at most crossings. This says that the average number of crossings per edge is at most (for every subgraph). Of course, a graph is planar if and only if it is -close to planar, and a graph has Euler genus at most if and only if it is -close to Euler genus . Graphs that can be drawn in the plane with at most crossings per edge, so called -planar graphs, are examples of graphs -close to planar. Pach and Tóth [69] proved that -planar graphs have average degree . It follows that -planar graphs are -colourable, which is best possible since is -planar. For defective colourings, three colours suffice even in the more general setting of graphs -close to Euler genus .

###### Theorem 4.4.

For all integers the class of graphs -close to Euler genus has defective chromatic number and defective choice number equal to 3. In particular, every graph -close to Euler genus is -choosable.

We prove this theorem by a series of lemmas, starting with a straightforward extension of the standard probabilistic proof of the crossing lemma. Note that Shahrokhi et al. [80] obtained a better bound for a restricted range of values for relative to .

###### Lemma 4.5.

Every drawing of a graph with vertices and edges on a surface of Euler genus has at least crossings.

###### Proof.

By Lemma 4.2, every -vertex graph that embeds in has at most edges. Thus every drawing of an -vertex -edge graph on has at least crossings.

Given a graph with vertices and edges and a crossing-minimal drawing of on , choose each vertex of independently and randomly with probability . Note that . Let be the induced subgraph obtained. The expected number of vertices in is , the expected number of edges in is , and the expected number of crossings in the induced drawing of is , where is the number of crossings in the drawing of . By linearity of expectation and the above naive bound, . Thus . ∎

This lemma leads to the following bound on the number of edges.

###### Lemma 4.6.

If an -vertex -edge graph has a drawing on a surface of Euler genus with at most crossings, then

 m⩽√8k+4dgn.
###### Proof.

If then , and we are done. Otherwise, , and Lemma 4.5 is applicable. Thus every drawing of on a surface of Euler genus has at least crossings. Hence , implying . ∎

To apply Theorem 2.3 we bound the size of subgraphs.

###### Lemma 4.7.

Every drawing of in a surface of Euler genus has at least

 t(t−1)(2g+3)(2g+2)

crossings.

###### Proof.

By Lemma 4.3, does not embed (crossing-free) in a surface of Euler genus . Consider a drawing of in a surface of Euler genus . There are copies of in . Each such copy has a crossing. Each crossing is in at most copies of . Thus the number of crossings is at least

 (t2g+3)/(t−22g+1)=t(t−1)(2g+3)(2g+2).

###### Lemma 4.8.

If a graph is -close to Euler genus and contains as a subgraph, then

 t⩽3k(2g+3)(2g+2)+1.
###### Proof.

Suppose that contains as a subgraph. Since is -close to Euler genus , so is . Thus has a drawing in a surface of Euler genus where the number of crossings is at most . By Lemma 4.7,

 t(t−1)(2g+3)(2g+2)⩽3kt.

The result follows. ∎

We now prove the main result of this section.

###### Proof of Theorem 4.4.

Say is a graph -close to Euler genus . By Lemma 4.8, contains no with . By Lemma 4.6, . We now bound . Consider a subgraph of that is a )-subdivision of a graph . Since is -close to Euler genus , so is . Thus has a drawing on a surface of Euler genus with at most crossings. Remove each division vertex and replace its two incident edges by one edge. We obtain a drawing of with the same number of crossings as the drawing of . Now . Thus has a drawing on a surface of Euler genus with at most crossings. By Lemma 4.6, . Hence . By Theorem 2.3, is -choosable, where

 d =⌊N1(3,3k(2g+3)(2g+2)+2,2√8k+4dg,2√16k+4dg)⌋−2 ⩽O((k+1)5/2(g+1)7/2).\qed

## 5. Thickness Parameters

This section studies defective colourings of graphs with given thickness or other related parameters. Yancey [91] first proposed studying defective colourings of graphs with given thickness.

### 5.1. Light Edge Lemma

Our starting point is the following sufficient condition for a graph to have a light edge. The proof uses a technique by Bose et al. [16], which we present in a general form.

###### Lemma 5.1.

Let be a graph with vertices, at most edges, and minimum degree , such that every spanning bipartite subgraph has at most edges, for some and and satisfying:

 (4) 2a⩾δ>a′, (5) (δ−a′)ℓ>(2a−a′)δ, and (6) (δ−a′)ℓ2−((2a−a′)δ+b′−δ+a′)ℓ−(2a−a′+2b−b′)δ>0.

Then has an -light edge.

###### Proof.

Let be the set of vertices with degree at most . Since vertices in have degree at least and vertices not in have degree at least ,

 δ|X|+(n−|X|)ℓ⩽∑v∈V(G)deg(v)=2|E(G)|⩽2(an+b).

Thus

 (ℓ−2a)n−2b⩽(ℓ−δ)|X|.

Suppose on the contrary that is an independent set in . Let be the spanning bipartite subgraph of consisting of all edges between and . Since each of the at least edges incident with each vertex in are in ,

 δ|X|⩽|E(G′)|⩽a′n+b′.

Since (hence ) and ,

 δ(ℓ−2a)n−2bδ ⩽δ(ℓ−δ)|X|⩽(ℓ−δ)(a′n+b′) ⇒ (δ(ℓ−2a)−a′(ℓ−δ))n ⩽(ℓ−δ)b′+2bδ ⇒ ((δ−a′)ℓ−(2a−a′)δ)n ⩽b′ℓ+(2b−b′)δ.

If then every edge is -light. Now assume that . Since ,

 ((δ−a′)ℓ−(2a−a′)δ)(ℓ+1)⩽b′ℓ+(2b−b′)δ.

Thus

 (δ−a′)ℓ2+(δ−a′−(2a−a′)δ−b′)ℓ⩽(2a−a′+2b−b′)δ,

which is a contradiction. Thus is not an independent set. Hence contains an -light edge. ∎

###### Remark.

To verify (6), the following approximation can be useful: If are strictly positive reals, then the larger root of is at most

 (7) β+√β(β+4αγβ)2α⩽β+12(β+(β+4αγβ))2α=βα+γβ.

Lemma 2.1 with and Lemma 5.1 imply the following sufficient condition for defective choosability. With , which is the minimum possible value for , the number of colours only depends on the coefficient of in the bound on the number of edges in a bipartite subgraph .

###### Lemma 5.2.

Fix constants and and satisfying (4), (5) and (6). Let be a graph such that every subgraph of with minimum degree at least satisfies the following conditions:

1. has at most edges.

2. Every spanning bipartite subgraph of has at most edges.

Then is -choosable. In particular, is -choosable.

Lemma 5.1 with and and and and implies that every graph with minimum degree at least and Euler genus has a -light edge. Note that this bound is within of being tight since has minimum degree 3, embeds in a surface of Euler genus , and every edge has an endpoint of degree . More precise results, which are typically proved by discharging with respect to an embedding, are known [48, 44, 9]. Lemma 5.2 then implies that every graph with Euler genus is -choosable. As mentioned earlier, this result with a better degree bound was proved by Woodall [90]; also see [19]. The utility of Lemma 5.2 is that it is immediately applicable in more general settings, as we now show.

### 5.2. Thickness

The thickness of a graph is the minimum integer such that is the union of planar subgraphs; see [63] for a survey on thickness. A minimum-degree-greedy algorithm properly -colours a graph with thickness , and it is an open problem to improve this bound for . The result of Havet and Sereni [38] implies that graphs with thickness , which have maximum average degree less than , are -choosable, but gives no result with at most colours. We show below that graphs with thickness are -choosable, and that no result with at most colours is possible. That is, both the defective chromatic number and defective choice number of the class of graphs of thickness at most equal . In fact, the proof works in the following more general setting. For an integer , the -thickness of a graph is the minimum integer such that is the union of subgraphs each with Euler genus at most . This definition was implicitly introduced by Jackson and Ringel [45]. By Euler’s Formula, every graph with vertices and -thickness has at most edges, and every spanning bipartite subgraph has at most edges. Lemma 5.1 with (using (7) to verify (6)) implies:

###### Lemma 5.3.

Every graph with minimum degree at least and -thickness at most has a -light edge.

We now determine the defective chromatic number and defective choice number of graphs with given -thickness.

###### Theorem 5.4.

For integers and , the class of graphs with -thickness at most has defective chromatic number and defective choice number equal to . In particular, every graph with -thickness at most is -choosable.

###### Proof.

Lemmas 5.3 and 5.2 imply the upper bound. As usual, the lower bound is provided by . We now prove that has -thickness at most by induction on (with fixed). Note that is planar, and thus has -thickness 1. Let be the vertex of such that is the disjoint union of copies of . For , let be the vertex of the -th component of such that is the disjoint union of copies of . Let . Observe that each component of is isomorphic to and by induction, has -thickness at most . Since consists of copies of pasted on for some , is planar and thus has -thickness 1. Hence has -thickness at most . By Lemma 2.4, has no -colouring. Therefore the class of graphs with -thickness at most has defective chromatic number and defective choice number at least . ∎

The case and relates to the famous earth–moon problem [3, 35, 43, 73, 45], which asks for the maximum chromatic number of graphs with thickness . The answer is in . The result of Havet and Sereni [38] mentioned in Section 1 implies that graphs with thickness 2 are -choosable, -choosable, -choosable, -choosable, and -choosable because their maximum average degree is less than . But their result gives no bound with at most 6 colours. Theorem 5.4 says that the class of graphs with thickness 2 has defective chromatic number and defective choice number equal to . In particular, Lemma 5.2 implies that graphs with thickness 2 are -choosable, -choosable, -choosable, -choosable, -choosable, -choosable, and -choosable. This final result, which is also implied by the result of Havet and Sereni [38], is very close to the conjecture that graphs with thickness 2 are 11-colourable. Improving these degree bounds provides an approach for attacking the earth–moon problem.

### 5.3. Stack Layouts

A -stack layout of a graph consists of a linear ordering of and a partition of such that no two edges in cross with respect to for each . Here edges and cross if . A graph is a -stack graph if it has a -stack layout. The stack-number of a graph is the minimum integer for which is a -stack graph. Stack layouts are also called book embeddings, and stack-number is also called book-thickness, fixed outer-thickness and page-number. The maximum chromatic number of -stack graphs is in ; see [30]. For defective colourings, colours suffice.

###### Theorem 5.5.

The class of -stack graphs has defective chromatic number and defective choice number equal to . In particular, every -stack graph is -choosable.

###### Proof.

The lower bound follows from Lemma 2.4 since an easy inductive argument shows that is a -stack graph for all . For the upper bound, is not a -stack graph [6]; see also [27]. Every -stack graph has average degree less than (see [51, 6, 30]) and (see [67]). The result follows from Theorem 2.3 with and , where . ∎

### 5.4. Queue Layouts

A -queue layout of a graph consists of a linear ordering of and a partition of such that no two edges in are nested with respect to for each . Here edges and are nested if . The queue-number of a graph is the minimum integer for which has a -queue layout. A graph is a -queue graph if it has a -queue layout. Dujmović and Wood [30] state that determining the maximum chromatic number of -queue graphs is an open problem, and showed lower and upper bounds of and . We provide the following partial answer to this question.

###### Theorem 5.6.

Every -queue graph is -choosable.

###### Proof.

Heath and Rosenberg [41] proved that is not a -queue graph. Every -queue graph has (see [41, 70, 30]) and (see [67]). The result then follows from Theorem 2.3 with and , where . ∎

Since has a -queue layout, the defective chromatic number of the class of -queue graphs is at least and at most by Lemma 2.4 and Theorem 5.6. It remains an open problem to determine its defective chromatic number.

### 5.5. Posets

Consider the problem of partitioning the domain of a given poset into so that each has small poset dimension. The Hasse diagram of is the graph whose vertices are the elements of and whose edges correspond to the cover relation of . Here covers in if , and there is no element of such that , , and . A linear extension of is a total order on such that implies for every . The jump number of is the minimum number of consecutive elements of a linear extension of that are not comparable in , where the minimum is taken over all possible linear extensions of .

###### Theorem 5.7.

For every integer there is an integer such that the domain of any poset with jump number at most


text:
Browse Questions

# The mid - points of two small magnetic dipoles of length d in end - on positions , are separated by a distance x, (x >> d) . The force between them is proportional to $\;x^{-n}\;$ where n is :

$(a)\;1\qquad(b)\;2\qquad(c)\;3\qquad(d)\;4$

Can you answer this question?

–1 vote


text:
Inequality involving abs. value of complex-valued multiple integral

1. Mar 10, 2006

benorin

How do I show that

$$0\leq \Re (s) +k\Rightarrow\left| (s)_k \int_0^1\cdots\int_0^1 (n+x_1+\cdots +x_k)^{-s-k}\, dx_1\cdots\, dx_k \right| \leq |(s)_k|n^{-\Re (s) -k}$$

where k is a nongegative integer and $$(s)_k:=s(s+1)\cdots (s+k-1)$$ is the Pochammer symbol (aka the rising factorial) ?

If it helps, I know (and have previously proven) that

$$(s)_k\int_0^1\cdots\int_0^1 (n+x_1+\cdots +x_k)^{-s-k}\, dx_1\cdots\, dx_k = \sum_{m=0}^{k}(-1)^{m} \left(\begin{array}{c}k\\m\end{array}\right) (n+m)^{-s} =: \Delta ^k (n^{-s})$$

where $$\Delta$$ is the forward difference operator.

Last edited: Mar 10, 2006
2. Mar 10, 2006

shmoe

You don't need your previous work, just use the simplest upper bound for your integral you can think of.

3. Mar 10, 2006

benorin

I got it. Thanks shmoe.


text:
## Chinese Telegraph Code (CTC)

Michael Rank has an interesting article on Scribd entitled "Chinese telegram, 1978" (5/22/2015).

It's about a 1978 telegram that he bought on eBay.  Here's a photograph:

Read the rest of this entry »

## Paperless reading

Just a little over a year ago, I made the following post:

The second half of that post consisted of an account of a lecture that David Moser (of Beijing Capital Normal University and Academic Director of Chinese Studies at CET Beijing) had delivered a few days earlier (on 4/1/14) at Penn:  "Is Character Writing Still a Basic Skill?  The New Digital Chinese Tools and their Implications for Chinese Learning".

Read the rest of this entry »

## Error-laden phishing attempts

Phishers trawling for email account names are generally smart enough to pull all sorts of programming tricks, forging headers and obtaining lists of spammable addresses and setting up arrangements to capture login names and passwords obediently typed in by the gullible; but then they give themselves away with errors of grammar and punctuation that are just too gross to be perpetrated by the authorized guys at the communications and technology services unit.

I received a phishing spam today that had no To-line at all (none of that "undisclosed recipients" stuff, and no mention of my email address in it anywhere). It looked sort of convincing in its announcement that webmail account holders would have to take certain steps to ensure the preservation of their address books after being "upgraded to a new enhanced Outlook interface". (My own university has, tragically, been induced to do an upgrade of this kind to its employee email services.) But the linguistic errors in the message begin with the 13th character in the From line (that second comma is wrong). I reproduce below the raw text of what I received, stripping out only the locally generated receipt and spam-checking headers (and by the way, this message—spam though it is—succeeded in getting a spam score of 0).

Read the rest of this entry »

Comments off

## Famous last words

Guest post by Karen Stollznow

In recent weeks we've been following the tragedy and mystery of the Malaysia Airlines flight 370 that vanished on March 8 with 239 people on board. Less than an hour after taking off from Kuala Lumpur en route to Beijing all communication was cut off. The plane diverted unexpectedly across the Indian Ocean and disappeared from civilian air traffic control screens. There has been much controversy surrounding the transcript of the last incoming transmission between the air traffic controller and the cockpit of the ill-fated flight.

We tend to have a morbid fascination with people's last words. We assign profound meaning and philosophical insights to the final words uttered by those who face their fate ahead of us. There are numerous books and websites that chronicle the linguistic legacies of famous people such as Douglas Fairbank's ironic, "I've never felt better," to Woodrow Wilson's courageous, "I am ready," and the betrayal expressed in Julius Caesar's "Et tu, Brute?" Planecrashinfo.com maintains a database of last words from cockpit recordings, transcripts, and air traffic control tapes. These are disturbing announcements of impeding doom, including: "Actually, these conditions don't look very good at all, do they?" through to an assortment of cuss words, and moving farewells like, "Amy, I love you."

Read the rest of this entry »

Comments off

## The sparseness of linguistic data

Gary Marcus and Ernest Davis say in a New York Times piece on why we shouldn't buy all the hype about the Big Data revolution in science:

Big data is at its best when analyzing things that are extremely common, but often falls short when analyzing things that are less common. For instance, programs that use big data to deal with text, such as search engines and translation programs, often rely heavily on something called trigrams: sequences of three words in a row (like "in a row"). Reliable statistical information can be compiled about common trigrams, precisely because they appear frequently. But no existing body of data will ever be large enough to include all the trigrams that people might use, because of the continuing inventiveness of language.

To select an example more or less at random, a book review that the actor Rob Lowe recently wrote for this newspaper contained nine trigrams such as "dumbed-down escapist fare" that had never before appeared anywhere in all the petabytes of text indexed by Google. To witness the limitations that big data can have with novelty, Google-translate "dumbed-down escapist fare" into German and then back into English: out comes the incoherent "scaled-flight fare." That is a long way from what Mr. Lowe intended — and from big data's aspirations for translation.

Read the rest of this entry »

Comments off

## The future of Chinese language learning is now

When I began learning Mandarin nearly half a century ago, I knew exactly how I wanted to acquire proficiency in the language.  Nobody had to tell me how to do this; I knew it instinctively.  The main features of my desired regimen would be to:

1. pay little or no attention to memorizing characters (I would have been content with actively mastering 25 or so very high frequency characters and passively recognizing at most a hundred or so high frequency characters during the first year)

2. focus on pronunciation, vocabulary, grammar, particles, morphology, syntax, idioms, patterns, constructions, sentence structure, rhythm, prosody, and so forth — real language, not the script

3. read massive amounts of texts in Romanization and, if possible later on (after about half a year when I had the basics of the language nailed down), in character texts that would be phonetically annotated

Read the rest of this entry »

## Swype and Voice Recognition for mobile device inputting

In late 2012, while visiting my son Tom in Dallas, I noticed that he was doing something very odd with his cell phone.  Most people enter text into their cell phone by pressing their thumbs (or their fingertip) on the letters of a small keyboard, whether virtual or actual.  But Tom was doing something altogether different:  he was sliding his finger over the glass surface of his phone and somehow, by so doing, he was able to enter text.  I was dumbfounded!  What amazed me most of all was how casual he was about it.  He'd be talking to me about something, then glance down at his cell phone, move his fingertip around on the glass, and — presto digito! — he'd have typed a message to someone and sent it off.

Read the rest of this entry »

I recently heard of another friend-of-a-friend case in which people were taken in by one of the false email help-I'm-stranded scams, and actually sent money overseas in what they thought was a rescue for a relative who had been mugged in Spain. People really do respond to these scam emails, and they lose money, bigtime. Today I received the first Nigerian spam I have seen in which I am (purportedly) threatened by the FBI and Patriot Act government if I don't get in touch and hand over personal details that will permit the FBI to release my $3,500,000. I wish there was more that people with basic common sense could do to spread the word about scamming detection to those who are somewhat lacking in it. The best I have been able to do is to write occasional Language Log posts pointing out the almost unbelievable degree of grammatical and orthographic incompetence in most scam emails. Sure, everyone makes the odd spelling mistake (childrens' for children's and the like), but it is simply astonishing that literate people do not notice the implausibility of customs officials or bank officers or police employees being as inarticulate as the typical scam email. The one I just received is almost beyond belief (though see my afterthought at the end of this post). The worst thing I can think of to do to the senders is to publish the message here on Language Log, to warn the unwary, and perhaps permit those who are interested to track the culprit down. I reproduce the full content of the message source below, with nothing expurgated except for the x-ing out of my email address and local server names. I mark in red font the major errors in grammar and punctuation, plus a few nonlinguistic suspicious features. Read the rest of this entry » Comments off ## The language of phone numbers What xkcd is getting at with the latest comic is about syntax and semantics. I'll show you the syntax below, but as far as meaning is concerned, the point is that cell phone numbers have almost no semantics. The area code part (the first three digits) used to function as a locational marker when phones were in fixed locations in houses, but since Americans not only tend to move every three years or so but they now take phone numbers with them, and cell phone universality only really began to pick up in America five to ten years ago, it really does tend to reflect a former abode. My cool son Calvin, for example, has a number which implies that he lives in Oakland, California; he doesn't, he does his video game programming in the Pacific North West. And the rest of the number, the other seven digits? Space enough there for some real personal information, but it is not used. It functions merely as arbitrary material to distinguish one cell phone's location point in the information universe from all the others. Read the rest of this entry » ## Noisily channeling Claude Shannon There's a passage in James Gleick's "Auto Crrect Ths!", NYT 8/4/2012, that's properly spelled but in need of some content correction: If you type “kofee” into a search box, Google would like to save a few milliseconds by guessing whether you’ve misspelled the caffeinated beverage or the former United Nations secretary-general. It uses a probabilistic algorithm with roots in work done at AT&T Bell Laboratories in the early 1990s. The probabilities are based on a “noisy channel” model, a fundamental concept of information theory. The model envisions a message source — an idealized user with clear intentions — passing through a noisy channel that introduces typos by omitting letters, reversing letters or inserting letters. “We’re trying to find the most likely intended word, given the word that we see,” Mr. [Mark] Paskin says. “Coffee” is a fairly common word, so with the vast corpus of text the algorithm can assign it a far higher probability than “Kofi.” On the other hand, the data show that spelling “coffee” with a K is a relatively low-probability error. The algorithm combines these probabilities. It also learns from experience and gathers further clues from the context. The same probabilistic model is powering advances in translation and speech recognition, comparable problems in artificial intelligence. In a way, to achieve anything like perfection in one of these areas would mean solving them all; it would require a complete model of human language. But perfection will surely be impossible. We’re individuals. We’re fickle; we make up words and acronyms on the fly, and sometimes we scarcely even know what we’re trying to say. Read the rest of this entry » ## Passport pickup by pinyin Yesterday I went to the Beijing Public Security Bureau (Gōng'ān jú 公安局) to renew my visa. While waiting in the main hall for my number to be called, I had ample time to walk around and familiarize myself with the operations there. One thing in particular piqued my curiosity. Namely, I saw four gray, metal cabinets full of hundreds of passports (three for Chinese, one for foreigners) waiting to be picked up. I watched a clerk filing passports into the slots on the mechanized, revolving shelves inside the cabinets. Wondering how the passports were arranged so that they could be readily retrieved when called for, I asked the supervisor how the passports were ordered on the shelves. Her reply left me both startled and pleased. Read the rest of this entry » ## The economics of Chinese character usage Under the above rubric, my friend Apollo Wu sent around a note (copied below) about the economic impact of the use of Chinese characters in the operation of his business. Since Apollo was for many years (from 1973 to 1998) a top translator in the Chinese Translation Service at United Nations headquarters in New York, he knows whereof he speaks. Among other interesting tidbits that I heard from Apollo over the decades was that, of the official languages of the United Nations (Arabic, Mandarin Chinese, English, French, Russian, and Castilian Spanish) Chinese was by far the least efficient and most expensive to process. Read the rest of this entry » ## Password strength We neglected to mention this while the relevant cartoon was the current one at xkcd, but a couple of days ago there was a nice analysis of why through 20 years of effort, we've successfully trained everyone to use passwords that are hard for humans to remember but easy for computers to guess. Check it out. The observation seems correct: if you try it out on one of the web interfaces that assess the strength of your password as you choose it, you'll find that a word with a few letters replaced by miscellaneous digits and so on, like Ne8r@$k@, gets high marks but grizzle snip grunt mackerel doesn't (and probably won't be accepted beyond the first 8 to 12 characters). Yet if you mutter "grizzle snip grunt mackerel" under your breath once, you'll find you remember it all day, even without using it. And length is your main security. The example the cartoon gives contrasts a 3-day brute-force cracking time (for about 28 bits of entropy) with a 550-year time (for about 44).

[Comments are closed unless you have a password. If you have forgotten your password, click here.]

Comments off


text:
Let $Q(\sqrt{\gamma})$ be the BER of a BPSK system over an AWGN channel with two-sided noise power spectral density $N_{0}/2.$ The parameter $\gamma$ is a function of bit energy and noise power spectral density.
A system with two independent and identical AWGN channels with noise power spectral density $N_{0}/2$ is shown in the figure. The BPSK demodulator receives the sum of outputs of both the channels.
If the BER of this system is $Q(\sqrt{\gamma})$ then the value of $b$ is _____.


text:
Update all PDFs

# Graphing Rational Functions

Alignments to Content Standards: F-IF.C.7.d

In this task we are going to investigate the graphs of $\displaystyle{f(x) = \frac{1}{x+a}}$ and $\displaystyle{g(x) = \frac{1}{x^2+b}}.$ Move the sliders below to change the values of $a$ and $b$.

1. Describe your observations.
2. Connect the features you observed on the graphs to the structure of the expressions of the functions.

## IM Commentary

This task starts with an exploration of the graphs of two functions whose expressions look very similar but whose graphs behave completely differently. At first glance this is surprising but can be explained by a closer look at the functions' expressions.

Important features of rational functions are vertical asymptotes, which can be found by computing the zeros of the denominator of the function. Since one family of functions has a linear expression in the denominator, each representative has exactly one vertical asymptote. The other family of functions has a quadratic expression in the denominator, which can have 0, 1 or 2 zeros for different values of $b$, therefore the graphs have 0, 1, or 2 asymptotes.

Students can make many observations by playing with the sliders in the desmos app. It is up to the instructor to decide which observations they would like to pursue. The important point of the task is to connect features of the graph with corresponding features or properties of the formulas. As a follow-up exercise, the instructor might be asked to give a rough sketch of a specific such function, or use the techniques described in the solution to sketch the graph of something like $y=\frac{1}{x^2+x}$.

This task is an illustration of SMP 7 - Look for and make use of structure. It could be used as an in-class activity or as a homework problem leading up to a classroom discussion.

## Solution

1. As $a$ changes, the graph of the function $f(x)$ shifts horizontally. The function has a vertical asymptote at $x=-a$, otherwise the functions are exactly the same.

As $b$ changes the graph of $g(x)$ takes on three different shapes. It either has no vertical asymptote when $b\gt0$, 1 asymptote when $b=0$ or 2 asymptotes when $b\lt0$.

There are many more observations students can make, e.g.: If $b$ get large then $g(x)$ hugs the line $y = 0$, or if $a$ and $b$ are the same positive number, then the functions cross the y axis at the same point. There are many others.

2. The denominator of $\displaystyle{\frac{1}{x+a}}$ is zero when $x=-a$. This is true for all values of $a$. Therefore, the graph of $\displaystyle{\frac{1}{x+a}}$ has one vertical asymptote at $x=-a$. If $a=0$ we have $\displaystyle{f(x)=\frac{1}{x}}$. We can obtain all other functions by computing $f(x+a)$ which is is a horizontal shift of $\displaystyle{\frac{1}{x}}.$

Depending on the value of $b$, the denominator of $\displaystyle{g(x)=\frac{1}{x^2+b}}$ has 0, 1, or 2 zeros.

• When $b\gt 0$ we have $x^2+b\gt 0$, so the denominator is never zero and therefore, the graph of $g(x)$ does not have any vertical asymptotes. As $b$ approaches zero, the bump in the graph gets higher and higher since the denominator gets smaller and approaches zero for $x$-values close to zero. As $b$ gets larger, the entire denominator gets larger and therefore $g(x)$ has values close to zero for all values of $x$.Therefore, the bump disappears and $g(x)$ hugs the $x$-axis.
• When $b=0$ the graph of $g(x)$ has only vertical asymptote $x=0$.
• When $0\gt b$ we have $x^2+b = (x-\sqrt{-b})(x+\sqrt{-b})$. Therefore the graph of $\displaystyle{g(x) = \frac{1}{(x-\sqrt{-b})(x+\sqrt{-b})}}$ has vertical asymptotes $x=\sqrt{-b}$ and $x=-\sqrt{-b},$ which move farther and farther apart as $b$ moves towards minus infinity.

The $y$-intercept of $f(x)$ is $f(0)=\frac{1}{a}$. The $y$-intercept of $g(x)$ is $g(0)=\frac{1}{b}$. If $a=b$ then the two functions have the same $y$-intercepts.


text:
# Incorrect indentation for the “end” word of a for loop

I'm writing a pseudo code in latex using algorithm package, however, I have problem with indentation of the last end word for the for-loop if this for-loop contains an if statement. If it doesn't contain the if statement, all looks fine.

Example with no if statement and correct indentation:

Example with an if statement and incorrect indentation:

The code used to generate the latter one is following (just remove the if part to get the code used for first example):

\begin{algorithm}[H]
\caption{Test algorithm}
\SetAlgoLined

\For{$t \in T$}{
$t \gets$ 1

\If{ (t) \in P} {
t \gets 0

}
}

\end{algorithm}

Do you know how can this be fixed? Thanks

• Are you sure about "using algorithm package"? The \SetAlgoLined seems to be introduced by the algorithm2e package. Could you please add a minimal working example (MWE) to your question? Also, do you recieve any error messages? If so, please don't ignore then. Even if you get something that on first glance resembles a pdf file, there can still be issues with it. After an error, TeX only tries to recover enough to syntax check more of the file, it does not try to make sensible output after an error. – leandriis Jul 7 at 16:56

From your usage of \SetAlgoLined I assume that you are actually using the algorithm2e package. If I make a MWE with this package, I recieve the following error message Missing $inserted. that is caused by \in and \gets being used in text mode in line 12 and 13. If I add the missing$s, the MWE compiles perfectly fine and gives the desired result:

\documentclass{article}
\usepackage[ruled]{algorithm2e}

\begin{document}
\begin{algorithm}[H]
\caption{Test algorithm}
\SetAlgoLined

\For{$t \in T$}{
$t \gets$ 1

\If{ $(t) \in P$} {
$t \gets 0$

}
}

\end{algorithm}
\end{document}
• Thanks a lot, that was exactly the problem and sorry for stating misleading package name! – leopik Jul 7 at 17:08


text:
# How to solve this trigonometric equation / geometric problem

Is there any way to solve this type of equation exactly for x, where a-h are precalculated constants:

$a\cos(g x)+b \sin(g x)+c\cos(h x)+d\sin(hx)+ex+f=0$

Or is my only/best option some sort of approximate or iterative solution?

Update: As it seems the above equation cannot be solved exactly but here's a description what I'm trying to achieve in terms of geometric problem, in hopes somebody knows a better approach (with solvable equation) for solving that underlying problem.

Basically I have two spheres of different sizes and angular velocities, moving towards each other alongside the x-axis (linear motion can be simplified to only one moving). Both spheres contain some specific point on their surface and what I'm trying to solve is the (first) time that those points hit some common point in regard to that x-axis. That is they both hit the green line in the picture below in regard to x-axis, even though they might be at different y positions within the line. So the x variable that I'm trying to solve can be thought of either as the time of impact or the location of that green line.

As a further complication, these are actually 3D-spheres so that the axis of rotation can be anything (combined rotations around two axes) and different between the spheres. The linear motion is alongside a single axis though.

But that in essence is what I tried to model with that trigonometric equation. That e*x term models the relative linear motion and there are sin/cos terms for both spheres for getting the change alongside the x-axis for the 3D-rotation.

Any ideas if there could be some other approach in solving that?

It's a transcendental equation. No matter how you combine the sin/cos terms, if you have $x$ outside and inside the trig/exp/log functions, there is no closed form analytic solution. You have to solve it numerically (e.g. iteration/bisection/Newton's method).

EDIT: reviewing your original problem, I think that you pretty much simplified as much as you can. Projecting the motion of the spheres to the $x$ axis, you have oscillating motion of both points, there's no way to simplify that. If the angular velocity were equal, it would make the equation easier to solve, but nothing more than that.

One of the problems is, that it's hard to predict even the number of solutions. You probably need to find the first intersection. You get a rough idea about its location if you set the radius of both spheres to $0$. This gives you an initial estimate that you can use to find the true minimum with bisection. The nice part is, that you get the exact upper and lower bound for the solution: set all cos/sin to 1 and express $x$ for one bound, and all to -1 to get the other bound. This gives you an interval for bisection. Then, you can just find the solution like this, but it may not be the lowest one. However, you know the period of both rotations. So you can split the interval into subintervals of maybe half the period of short/long rotation (it sort of depends on which radius is the bigger and more important) and try with bisection on each of them. This way you ensure the first solution.

I wouldn't recommend Newton's method, at least not until you get really close to the solution. For oscillatory functions, it tends to escape away from the solution.

In summary: in both limits, the solution is easy. For $a,b,c,d\to 0$, you get the "average" intersection from linear motion. If you "sit" at the average intersection, freeze the linear motion and only rotate one of the spheres, you get regular periodic solutions with $\arctan$. The reality is a mixture: when they are in the intersection zone, they may have a few intersections, roughly periodic, but the origin moves away until you don't get any new solutions.

This is what can suggest to your intuition that there are no analytic solutions. This complexity of a transitional phenomenon where you get a couple of grouped solutions and nothing else, is hard to imagine in an analytic form.

Sorry, I wish I had better news.

• Thank you. That's what I thought/feared. I updated the description above in case there's some fundamentally better approach to the underlying problem. – JohnDoeNot Mar 28 '14 at 20:47
• Thank you again for a comprehensive answer. Obviously it's not what I hoped for but at least it is a confirmation that I didn't miss something obvious and the problem itself truly is a hard one without exact solution. And also thank you for giving me directions how to continue. – JohnDoeNot Mar 31 '14 at 10:37


text:
# how did they get this answer for the words that don't have bba and abb?

I am looking at the answer in solution manual which asked , all the words that don't have both substring bba and abb.

and the answer was a*(baa*)*b+b*(a*ab)*a*

and I'm like wait a minute is that right ? but that can't make abb, which is in the language. So it's gotta wrong.

so I came up with my own , would this be all the words that don't have both substring bba and abb ?

(b+^)(ab+a)*+b*

^ is an empty string by the way

The textbook's answer does appear to be incorrect, as you note it does not generate $abb$ (and just to rule out an alternative interpretation of the exercise - "all strings that include neither $abb$ nor $bba$ - it does generate $bba$).

However your answer is also incorrect unfortunately - it doesn't generate $bba$.

There are a couple of reasonably sensible ways to get a correct answer (of course there's always many many techniques, and different people prefer different ones).

The first is the "intuition" approach, break the problem into the two parts, "the strings that don't have $bba$" and "the strings that don't have $abb$", then combine. With this method you have to then think about how such strings would look, and convince yourself that you haven't missed any cases.

The very formal method is to construct the expression from smaller, verifiable building blocks. In this case, we can easily construct a DFA for the strings that do contain $abb$ and one for the strings that contain $bba$, then we can use the intersection construction to get a DFA for the intersection of the two languages, take the complement DFA, then convert this to a regular expression.

What they seem to have done, and messed up or made a typo in one part, is the formal-but-not-quite-as-silly-as-option-2 method, where we make the two small DFAs, take their complements separately, convert each to a regular expression, then combine. I'll do the half that they seem to have gotten wrong (the bit that allows $abb$ but not $bba$, which is the first half of their expression).

The initial DFA is:

Taking the complement we get:

This second DFA recognises all the strings that don't contain $bba$. Now we convert this to a regular expression using the normal state elimination algorithm. If you haven't seen this yet, it will appear shortly in whatever course you're studying, or you can look over this explanation, but for the moment (and for the sake of keeping this answer on track!) hopefully it's acceptable that there is an algorithm for doing this conversion. In principle this algorithm can result in slightly different regular expressions depending on the order you eliminate the states, so if you have a go at it, you may not end up with quite the same regular expression (if you try one particular order, you get a real mess).

After all that we get the regular expression: $$(a+ba)^{\ast}b^{\ast}$$

If we then proceed and do the DFA for strings containing $abb$, take its complement and derive the regular expression, we get (picking the right elimination ordering) the same as their second half, $b^{\ast}(a^{\ast}ab)^{\ast}a^{\ast}$, and combine them and get the final answer: $$(a+ba)^{\ast}b^{\ast}+b^{\ast}(a^{\ast}ab)^{\ast}a^{\ast}$$

Do not have substrings bba and abb:

Regular Expression= ^+b+ bbb*+(a+ba)(a+ba)*(^+b)

L={^, a, b, aa, ab, ba, bb, aaa, aab, aba, baa, bab, bbb, aaaa, aaab, abaa, baaa, baab, baba, bbbb,...}

• This regular expression generates strings not containing $a$s. And strings starting with $b$, and at least one $a$ separating additional $b$s, if any. What about, say, $bbab$? $ab$, $abb$? – greybeard Aug 21 '20 at 0:23
• Thanks greybeard for pointing out the missing strings. Pl. check the corrected regular expression: Regular Expression= ^+b+ bbb*+(a+ba)(a+ba)*(^+b) L={^, a, b, aa, ab, ba, bb, aaa, aab, aba, baa, bab, bbb, aaaa, aaab, abaa, baaa, baab, baba, bbbb,...} – Ankit Rajpal Aug 22 '20 at 6:08
• (I think the list should show abab.) The first part looks redundant - $b^*$ covers strings not containing $a$s* nicely. Same for $(a+ba)(a+ba)^*$: why not allow the empty string once more? Now, I see *strings not containing $a$s*, and *strings not containing $bb$ - what about $abb$ and $bba$ (not containing "the other one")? – greybeard Aug 22 '20 at 9:50
• Yes..abab will also be accepted by the given regular expression. I don't see any reason of including empty string again. The question says that both abb and bba should not occur as a substring and the given regular expression is satisfying this requirement. – Ankit Rajpal Aug 23 '20 at 10:35
• I am under the impression you read words that don't have both substring $bba$ and $abb$ different from David Richerby(&me): may contain each, but not contain both of $bba$ and $abb$. (So, the list should include each - didn't check the three symbol strings.) – greybeard Aug 23 '20 at 10:54

These are incorrect R.E we generate bba from the 2nd part

I think b*+a*(ab)a+a*(ba)a+a*ba(a+ab)a+a*ab(a+ab)a may be correct R.E.

• $bba$ doesn't contain both of $bba$ and $abb$, so it should match the regular expression. I think you've misunderstood the question. – David Richerby Feb 23 '17 at 13:07

It is a very simple RE. {a*(ba+a)*(b+^) + (b *) } Where ^ is null. JazakAllah :)

• It is b* in the last. – Sheikh Ahsan Ali Dec 4 '19 at 13:52


text:
Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR13-138 | 31st October 2013 20:16

#### Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball

Revision #1
Authors: Itai Benjamini, Gil Cohen, Igor Shinkar
Accepted on: 31st October 2013 20:16
Keywords:

Abstract:

We construct a bi-Lipschitz bijection from the Boolean cube to the Hamming ball of equal volume. More precisely, we show that for all even $n \in {\mathbb N}$ there exists an explicit bijection $\psi \colon \{0,1\}^n \to \left\{ x \in \{0,1\}^{n+1} \colon |x| > n/2 \right\}$ such that for every $x \neq y \in \{0,1\}^n$ it holds that
$\frac{1}{5}\leq \frac{distance(\psi(x),\psi(y))}{distance(x,y)} \leq 4,$
where $distance(\cdot,\cdot)$ denotes the Hamming distance. In particular, this implies that the Hamming ball is bi-Lipschitz transitive.

This result gives a strong negative answer to an open problem of Lovett and Viola [CC 2012], who raised the question in the context of sampling distributions in low-level complexity classes. The conceptual implication is that the problem of proving lower bounds in the context of sampling distributions will require some new ideas beyond the sensitivity-based structural results of Boppana [IPL 97].

We study the mapping $\psi$ further and show that it (and its inverse) are computable in DLOGTIME-uniform $\mathbf{TC^{0}}$, but not in $\mathbf{AC^{0}}$. Moreover, we prove that $\psi$ is approximately local'' in the sense that all but the last output bit of $\psi$ are essentially determined by a single input bit.

Changes to previous version:

Mainly added a reference communicated to us by Viola.

### Paper:

TR13-138 | 5th October 2013 15:45

#### Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball

TR13-138
Authors: Itai Benjamini, Gil Cohen, Igor Shinkar
Publication: 8th October 2013 08:40
Keywords:

Abstract:

We construct a bi-Lipschitz bijection from the Boolean cube to the Hamming ball of equal volume. More precisely, we show that for all even $n \in {\mathbb N}$ there exists an explicit bijection $\psi \colon \{0,1\}^n \to \left\{ x \in \{0,1\}^{n+1} \colon |x| > n/2 \right\}$ such that for every $x \neq y \in \{0,1\}^n$ it holds that
$\frac{1}{5}\leq \frac{distance(\psi(x),\psi(y))}{distance(x,y)} \leq 4,$
where $distance(\cdot,\cdot)$ denotes the Hamming distance. In particular, this implies that the Hamming ball is bi-Lipschitz transitive.

This result gives a strong negative answer to an open problem of Lovett and Viola [CC 2012], who raised the question in the context of sampling distributions in low-level complexity classes. The conceptual implication is that the problem of proving lower bounds in the context of sampling distributions will require some new ideas beyond the sensitivity-based structural results of Boppana [IPL 97].

We study the mapping $\psi$ further and show that it (and its inverse) are computable in DLOGTIME-uniform $\mathbf{TC^{0}}$, but not in $\mathbf{AC^{0}}$. Moreover, we prove that $\psi$ is approximately local'' in the sense that all but the last output bit of $\psi$ are essentially determined by a single input bit.

ISSN 1433-8092 | Imprint


text:
<noframes id="r1bpv">

<meter id="r1bpv"></meter>
Paul's Online Notes
Home / Calculus I / Limits
Show Mobile Notice Show All Notes Hide All Notes
Mobile Notice
You appear to be on a device with a "narrow" screen width (i.e. you are probably on a mobile phone). Due to the nature of the mathematics on this site it is best views in landscape mode. If your device is not in landscape mode many of the equations will run off the side of your device (should be able to scroll to see them) and some of the menu items will be cut off due to the narrow screen width.

## Chapter 2 : Limits

The topic that we will be examining in this chapter is that of Limits. This is the first of three major topics that we will be covering in this course. While we will be spending the least amount of time on limits in comparison to the other two topics limits are very important in the study of Calculus. We will be seeing limits in a variety of places once we move out of this chapter. In particular we will see that limits are part of the formal definition of the other two major topics.

Here is a list of topics that are in this chapter.

Tangent Lines and Rates of Change –In this section we will introduce two problems that we will see time and again in this course : Rate of Change of a function and Tangent Lines to functions. Both of these problems will be used to introduce the concept of limits, although we won't formally give the definition or notation until the next section.

The Limit – In this section we will introduce the notation of the limit. We will also take a conceptual look at limits and try to get a grasp on just what they are and what they can tell us. We will be estimating the value of limits in this section to help us understand what they tell us. We will actually start computing limits in a couple of sections.

One-Sided Limits – In this section we will introduce the concept of one-sided limits. We will discuss the differences between one-sided limits and limits as well as how they are related to each other.

Limit Properties – In this section we will discuss the properties of limits that we’ll need to use in computing limits (as opposed to estimating them as we've done to this point). We will also compute a couple of basic limits in this section.

Computing Limits – In this section we will looks at several types of limits that require some work before we can use the limit properties to compute them. We will also look at computing limits of piecewise functions and use of the Squeeze Theorem to compute some limits.

Infinite Limits – In this section we will look at limits that have a value of infinity or negative infinity. We’ll also take a brief look at vertical asymptotes.

Limits At Infinity, Part I – In this section we will start looking at limits at infinity, i.e. limits in which the variable gets very large in either the positive or negative sense. We will concentrate on polynomials and rational expressions in this section. We’ll also take a brief look at horizontal asymptotes.

Limits At Infinity, Part II – In this section we will continue covering limits at infinity. We’ll be looking at exponentials, logarithms and inverse tangents in this section.

Continuity – In this section we will introduce the concept of continuity and how it relates to limits. We will also see the Intermediate Value Theorem in this section and how it can be used to determine if functions have solutions in a given interval.

The Definition of the Limit – In this section we will give a precise definition of several of the limits covered in this section. We will work several basic examples illustrating how to use this precise definition to compute a limit. We’ll also give a precise definition of continuity.

天天干夜夜爱 天天色播 天天射天天舔 <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <文本链> <文本链> <文本链> <文本链> <文本链> <文本链>


text:
# How do you convert 3sqrt(3) + 3i to polar form?

May 26, 2016

The result is $\left(6 , 0.52\right)$.

#### Explanation:

To convert a number from complex form to polar form you have simply to apply the definitions of sin and cos.

First of all we use the real part of the number ($3 \sqrt{3}$) as the $x$ coordinates and the imaginary part (without the $i$, so only $3$) as the $y$ and we put this on two axis as in the figure.

The polar form is nothing but $r$ and $\theta$.
$r$ can be obtained easily applying the Pitagora's theorem:

$r = \sqrt{{\left(3 \sqrt{3}\right)}^{2} + {3}^{2}} = \sqrt{27 + 9} = \sqrt{36} = 6$.

$\theta$ can be calculated using the definition of cosine or sine.
We know that $x = r \cos \left(\theta\right)$ and $y = r \sin \left(\theta\right)$. We could then say, for example, that $\sin \left(\theta\right) = \frac{y}{r}$ and then $\theta = \arcsin \left(\frac{y}{r}\right)$.
In the same way we can say $\theta = \arccos \left(\frac{x}{r}\right)$. But my favorite consists in dividing the two coordinates having

$\frac{y}{x} = \sin \frac{\theta}{\cos} \left(\theta\right)$ and because $\sin \frac{\theta}{\cos} \left(\theta\right) = \tan \left(\theta\right)$ we have $\frac{y}{x} = \tan \left(\theta\right)$ and finally

$\theta = \arctan \left(\frac{y}{x}\right)$. In our case $\theta = \arctan \left(\frac{3}{3 \sqrt{3}}\right) = \arctan \left(\frac{1}{\sqrt{3}}\right) \setminus \approx 0.52$.
Then your polar coordinates are $\left(6 , 0.52\right)$.
To see if the result is correct, you can transform back your number as:

$r \cos \left(\theta\right) + i r \sin \left(\theta\right) = 6 \cos \left(0.52\right) + i \cdot 6 \sin \left(0.52\right) = 5.19 + 3 i$ and 5.19 is the approximation of $3 \sqrt{3}$.


text:
Water Level

Geometry Level 2

A sphere of radius 6cm is dropped into a cylindrical vessel partly filled with water. The radius of the vessel is 8cm. If the sphere is submerged completely, then the surface of the water rises by

×


text:
## anonymous 5 years ago how would you intergate sqrt{s+t}ds dt

1. anonymous

there shouldn't be 2 d's?

2. anonymous

Never seen that before.

3. anonymous

$\int\limits_{0}^{1} \int\limits_{0}^{1} \sqrt{s+t} ds dt$

4. anonymous

Oh you take the intergral of the inside and then take the interal of the whole thing..

5. anonymous

oh no but it is both terms... hmm..

6. anonymous

It's some 3D plot http://www.wolframalpha.com/input/?i=integrate+sqrt%28s%2Bt%29ds+dt+

7. anonymous

so would you set one as a contasnt then intgrate to s then plug in and solve and integrate to t, but i don"t remenber how to intergrate a sqrt

8. anonymous

you just write the sqrt as x^1/2, and then you have 2/3x^3/2

9. anonymous

I have no idea how you would integrate that tho.. there are 2 variables... you would need an equation to define s in term of t or vise versa... I think the problem is from multi variable calc, which I am not familiar with at all.

10. anonymous

it is, but thank you anyway

11. anonymous

are you in college?

12. anonymous

yes it is cacl 4 homework problem

13. anonymous

i see i see... im taking calc 3 next quarter.. and probably calc 4 after that.

14. anonymous

so your doing all the sequnces and series stuff, and polar stuff now then or no

15. anonymous

Im taking the BC test in like a week, so I'm doing all that now.

16. anonymous

whats is bc, your calc 2 must be different

17. anonymous

calc3

18. anonymous

Its the high school version of calc... BC is calc 1 and 2. calc 3 is in college.

19. anonymous

okay, yea i did that same stuff in high school, still had to take it over in once i got to college, kinda sucked


text:
# State true or false -3 > -13

State true or false -3 > -13
You can still ask an expert for help

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

faldduE
We know that negative number which is closer to zero is bigger. If magnitude of a negative number is less than magnitude of other negative number then negative number having less magnitude is greater. (Here, magnitude means distance of number from zero). Here, magnitude of -3 is 3 and magnitude of -13 is 13. We know, 3<13 . Therefore, -3>-13. Hence, given statement is true.


text:
# positive semi definite matrix problem

Let $A$ be a $p\times p$ positive semi definite matrix.

(1) If $A$ is positive definite, and $B$ is a $p\times q$ matrix with rank $p\leq q$. Show that $B^TAB$ is positive definite.

(2) If $rankA=s\leq p$. Show that there exists a $p\times s$ matrix $M$ such that $A=MM^T$ and $M^TM$ is a diagonal matrix of the positive eigenvalues of A.

I don't even know how to start. Can someone give some hints?

-

For part (1), consider the fact that $A$ being positive definite means $$\mathbf{x}^\mathrm{T}A\mathbf{x} > 0$$ for all $\mathbf{x}$. Can you conclude something similar with $B^\mathrm{T}AB$?
(1) I think what you mean is that $B^TAB$ is positive semi-definite, which is easy to show if notice that $$B^TAB=B^TA^{1/2}A^{1/2}B=(A^{1/2}B)^TA^{1/2}B,$$ where $A^{1/2}$ is the square root of $A$, so ${A^{1/2}}^T=A^{1/2}$.