Analytic and Probabilistic Methods

the sums from Problem 1.1.6 (1);

the sums from Problem 1.1.6 (2);

the sums from Problem 1.1.6 (3);

the number $A_n$ of subsets of the set $\left\{ 1, 2, \ldots , n\right\}$ containing no two consecutive numbers;

the same as in part (4), for three consecutive numbers.

$\ex_{P_k}(n) \gtrsim \dfrac {k-2}{2} \cdot n$.

$\ex_{C_{2k+1}}(n) \gtrsim \dfrac {n^2}{4}$.

$\ex_{K_{1,k}}(n) \sim \dfrac {k-1}{2} \cdot n$.

$n^2\left(2+\dfrac {1}{n}\right)^n = (2+o(1))^n$. By definition, this means that there exists a function $\psi (n) = o(1)$ such that

or, equivalently,

$3^{\sqrt{n}}\left(2+\dfrac {1}{n}\right)^n = (2+o(1))^n$.

Find the asymptotics of $\sqrt[n]{\dbinom {n}{[n/2]}}$ (cf. Problems 1.4.3 (2) and 6.1.10 (2)).

$\dfrac {2^n}{n+1} < \dbinom {n}{[n/2]} < 2^n$.

Find the asymptotics of $\sqrt[m]{\dbinom {3m}{m}}$.

$\dfrac {3^{3m}}{3m+1} < 2^{2m}\dbinom {3m}{m} < 3^{3m}$.

$\dbinom {n}{[an]} = (a^{-a}(1-a)^{a-1}+o(1))^n$, where $0 < a < 1$.

$\dfrac {n!}{[a_1n]!\ldots [a_sn]!} = (e^{-a_1\ln a_1 - \ldots - a_s\ln a_s}+o(1))^n$, where $a_1+\ldots +a_s=1$, $0 < a_k < 1$.

Find the asymptotics of $\ln (n!)$.

Find the asymptotics of $\sqrt[n]{n!}$.

$n^ne^{-n+1} \leqslant n! \leqslant n^{n+1}e^{-n+1}$;

$n! \leqslant n^ne^{-n+1}\sqrt{n}$.

Stirling’s formula. $n! \sim n^ne^{-n}\sqrt{2\pi n}$, i.e., $\lim_{n \to \infty } \dfrac {n!}{n^ne^{-n}\sqrt{2\pi n}} = 1$.

$\dbinom {n}{k} < \dfrac {n^k}{k!}$.

$\ln \dfrac {(n-1)(n-2)\ldots (n-k)}{n^k} = -\dfrac {k(k+1)}{2n}\left(1+O\left(\dfrac {k}{n}\right)\right)$ for $k=k_n < \dfrac {n}{2}$.

This means that there exists a function $\psi (n) = O\left(\dfrac {k}{n}\right)$ such that

or, equivalently,

$\dbinom {n}{k} = \dfrac {n^k}{k!}e^{-\frac{k(k-1)}{2n}+O(k^3/n^2)}$ for $k=k_n < \dfrac {n}{2}$.

(Formulate yourself what $e^{-\frac{k(k-1)}{2n}+O(k^3/n^2)}$ means here.)

$\dbinom {n}{k} \sim \dfrac {n^k}{k!}$ for $k=k_n=o(\sqrt{n})$.

$\dbinom {2n}{n-k}\Big/\dbinom {2n}{n} = e^{-\frac{k^2}{n}(1+o(1))}$ for $k=k_n=o(n)$.

(Formulate yourself what $e^{-\frac{k^2}{n}(1+o(1))}$ means here.)

Is it true that the notations $e^{o(n)}$ and $o(e^n)$ are ``equivalent''?

That is, is it true that for any function $f : \mathbb {Z} \to (0,+\infty )$ the conditions $\lim_{n\to \infty }\dfrac {\ln f(n)}{n}=0$ and $\lim_{n\to \infty }f(n)e^{-n}=0$ are equivalent?

Find functions $f,g : \mathbb {Z} \to (0,+\infty )$ such that $f(n)\sim g(n)$, but $e^{f(n)} \neq O(e^{g(n)})$.

Can functions $f,g : \mathbb {Z} \to (0,+\infty )$ simultaneously satisfy the relations $f(n)=o(g(n))$ and $g(n)=o(f(n))$?

Can functions $f,g : \mathbb {Z} \to (0,+\infty )$ simultaneously satisfy the relations $f(n)=O(g(n))$ and $g(n)=O(f(n))$?

Do the two relations of part (4) imply that $f(n)\sim g(n)$?

Which function grows faster: $x^{(x^x)}$ or $(x!)^{(2^x)}$?

That is, find $\lim_{x\to \infty } x^{(x^x)}(x!)^{(-2^x)}$.

Does there exist a function $\psi (n) = o(1)$ such that $(2+\psi (n))^n \times 2^{-n}e^{-\sqrt{n}} \to \infty$?

(As in any mathematical problem, the answer must be justified: give an example of such a function, or prove its existence, or prove that no such function exists.)

$\ln \dbinom {n^2}{n}$;

$\dbinom {n}{[n/2]}$;

$\dbinom {n^2}{n}$;

$\dbinom {n}{[n^\alpha ]}$, $\alpha \in (0,1)$;

$(2n-1)!! := (2n-1)\cdot (2n-3)\cdot \ldots \cdot 3\cdot 1$;

$\displaystyle \sum_{k=0}^{n}\dbinom {n}{k}^2$;

$\displaystyle \sum_{k=0}^{n}\dbinom {n}{k}^4$.

$s^s = n$;

$s^{s^3} = n$;

$s(n) := \max \left\{ k : k! \leqslant n\right\}$;

$s(n) := \min \left\{ m \in \mathbb {N} : \dbinom {n}{m} < 2^{\binom {m}{2}}\right\}$ (cf. Problem 4.1.5);

$s(n) := \min \left\{ m \in \mathbb {N} : \dfrac {2^m}{m} > n\right\}$ (the function $2^m/m$ arises as the complexity of realizing Boolean functions);

$s(n) := \min \left\{ m \in \mathbb {N} : \dbinom {m}{[m/2]} > n\right\}$ (cf. Problem 1.4.3 (2)).

the number of linear subspaces of $\mathbb {Z}_2^n$ (see Problem 1.4.7 and the definition preceding it);

the number of unicyclic graphs with $n$ vertices (see Problem 2.2.5 (2) and the definition preceding it).

For each of 100 types of work, a company has exactly 8 specialists. An employee may be a specialist in several types of work; the assignment of specialists to types of work is known to the person who schedules days off. Each employee must be given a day off on either Saturday or Sunday. Prove that this can be done so that on both Saturday and Sunday, for each type of work, a specialist in it is at work. (This is Problem 1.6.7.)

For each of several types of work, a company has exactly 8 specialists. (Now the number of types of work need not be 100.) Each type of work shares specialists with at most 30 other types. Each employee must be given a day off on either Saturday or Sunday. Prove that this can be done so that on both Saturday and Sunday, for each type of work, a specialist in it is at work.

200 students from 10 groups, each of which has 20 students, stand in a circle. Prove that one can choose a leader in each group so that no two leaders stand next to each other.

The same for 1600 students from 100 groups, each of which has 16 students.

Prove that the first 8 positive integers can be colored in 2 colors so that there is no monochromatic arithmetic progression of length 3.

Prove that the first 15 million positive integers can be colored in 2 colors so that there is no monochromatic arithmetic progression of length 32.

Prove that for any $M \in \mathbb {R}$ all real numbers can be colored in 2 colors so that for any $x \in \mathbb {R}$ the numbers $x$ and $x+M$ have different colors.

Prove that for any 25 distinct numbers $M_1,\ldots ,M_{25} \in \mathbb {R}$ all real numbers can be colored in 3 colors so that for any $x \in \mathbb {R}$ the numbers $x+M_1,\ldots ,x+M_{25}$ include numbers of each of the three colors.

In the set of all squares of a chessboard, the subset of squares in its first three rows and the subset of squares in its last four columns.

The subsets $\left\{ 1,2\right\} \subset \left\{ 1,2,3,4\right\}$ and $\left\{ 1,3\right\} \subset \left\{ 1,2,3,4\right\}$.

The subsets $\left\{ 1,2\right\} \subset \left\{ 1,2,3,4,5,6\right\}$ and $\left\{ 1,3\right\} \subset \left\{ 1,2,3,4,5,6\right\}$.

The subset of numbers divisible by 5 and the subset of numbers divisible by 7.

The subset of numbers divisible by 15 and the subset of numbers divisible by 21.

The subset of numbers divisible by 15 and the subset of numbers divisible by 5.

The subset of numbers divisible by 10 and the subset of numbers divisible by 7.

The subset of colorings for which $\left\{ 1,2,\ldots ,8\right\}$ is monochromatic and the subset of colorings for which $\left\{ 11,12,\ldots ,18\right\}$ is monochromatic.

The subset of colorings for which $\left\{ 1,2,\ldots ,8\right\}$ is not monochromatic and the subset of colorings for which $\left\{ 11,12,\ldots ,18\right\}$ is not monochromatic (cf. Problem 6.2.1 (2)).

The subset of colorings for which $\left\{ 1,2,\ldots ,8\right\}$ is monochromatic and the subset of colorings for which $\left\{ 6,7,\ldots ,13\right\}$ is monochromatic.

Must there be a rich, healthy, smart citizen if in a city the proportion of rich citizens is greater than $\dfrac {2}{3}$, the proportion of healthy ones is greater than $\dfrac {2}{3}$, and the proportion of smart ones is greater than $\dfrac {2}{3}$?

The same question if the city has a rich citizen, a healthy citizen and a smart citizen, wealth, health and intelligence are pairwise independent, and the proportion of rich healthy smart citizens among the rich healthy ones is the same as the proportion of smart citizens among all inhabitants. (Together with the pairwise independence condition, the latter is called mutual independence.)

The same question if more than half of the citizens are rich, more than half are healthy, more than half are smart, wealth and intelligence are independent, and health and intelligence are independent.

Let $A_1,A_2,A_3,A_4$ be subsets of a 720-element set, each of which has more than 480 elements. If $A_k$ and $A_{k+1}$ are independent for every $k=1,2,3$, then $A_1\cap A_2\cap A_3\cap A_4 \neq \emptyset$.

Let $n \geqslant 2$ and let $A_1,A_2,\ldots ,A_n$ be subsets of a finite set, the proportion of each of which is greater than $1-\dfrac {1}{n-1}$. If $A_k$ and $A_{k+1}$ are independent for every $k=1,2,\ldots ,n-1$, then $A_1\cap A_2\cap \ldots \cap A_n \neq \emptyset$.

pairwise independent, but such that $A$ is not independent of the collection $B_1, B_2$;

not pairwise independent, but such that $A$ is independent of the collection $B_1, B_2$.

The Lovász local lemma in symmetric form. Let $A_1,\ldots ,A_n$ be subsets of a finite set. If for some $d$ and every $k$ the proportion of the subset $A_k$ is at least $1-\dfrac {1}{4d}$ and there exists a collection of at least $n-d$ subsets $A_j$ of which $A_k$ is independent, then $A_1\cap \ldots \cap A_n \neq \emptyset$.

For $d > 2$, the statement of part (1) remains true if $1-\dfrac {1}{4d}$ is replaced by $1-\dfrac {1}{e(d+1)}$.

If $a_k=1$ for every $k\leqslant 0$ and for some $d\geqslant 2$ the inequality $a_{k+1}\geqslant a_k-\dfrac {a_{k-d}}{4d}$ holds for every $k\geqslant 0$, then $a_k > 0$ for every $k$.

$k \geqslant 10$;

$k=9$

For any partition of the vertex set of a cycle of length $16n$ into $n$ sets of 16 vertices each, one can choose one vertex from each set so that there are no edges between the chosen $n$ vertices.

The same for $11n$ vertices.

In a graph, the degree of every vertex does not exceed $\Delta$. All the vertices are colored in $r$ colors. There are at least $2e\Delta +1$ vertices of each color. Then one can choose $r$ vertices of different colors, no two of which are joined by an edge.

Every $k$-element arithmetic progression in $\left\{ 1,2,\ldots ,n\right\}$ is intersected by at most $k^2\left[\dfrac {n}{k-1}\right]$ other such progressions.

For every positive integer $k$ there exists a coloring of the first $\left[\dfrac {2^{k-3}(k-1)}{k^2}\right]$ positive integers in 2 colors for which there is no monochromatic $k$-element arithmetic progression.

Every $k$-element arithmetic progression in $\left\{ 1,2,\ldots ,n\right\}$ is intersected by at most $nk$ other such progressions.

For every positive integer $k$ there exists a coloring of the first $\left[\dfrac {2^{k-3}}{k}\right]$ positive integers in 2 colors for which there is no monochromatic $k$-element arithmetic progression.

If $X\subset \mathbb {R}$ is a finite set and $m,r$ are positive integers such that $4rm(m-1)\left(1-\dfrac {1}{r}\right)^m < 1$, then for any $m$-element subset $M\subset \mathbb {R}$ there exists a coloring of $\mathbb {R}$ in $r$ colors such that for any $x\in X$ the set $x+M := \left\{ x+a : a\in M\right\}$ contains points of each of the $r$ colors.

The same for $X=\mathbb {Z}$.

The same for $X=\mathbb {R}$.

If $\dbinom {n}{2}\dbinom {k}{n-2}+1 < 2^{\binom {n}{2}-1}/e$, then $R(n,n) > k$, where $R(n,n)$ is the Ramsey number (Sec. 4.1).

$R(n,n) \gtrsim \sqrt{2}e^{-1}n2^{n/2}$. (Cf. Problem 4.1.5.)

Lovász local lemma. *Let $A_1,\ldots ,A_n$ be subsets of a finite set, $J_1,\ldots ,J_n\subset \left\{ 1,\ldots ,n\right\}$, and $\gamma_1,\ldots ,\gamma_n\in (0,1)$. Suppose also that for any $k$

• the proportion of the subset $A_k$ is at least $1-(1-\gamma_k)\displaystyle \prod_{j\notin J_k}\gamma_j$;

• the set $A_k$ is independent of the collection $\left\{ A_j : j\in J_k\right\}$.

Then the proportion of the intersection $\displaystyle \bigcap_{k=1}^{n}A_k$ is at least $\displaystyle \prod_{k=1}^{n}\gamma_k > 0$.*

There exists $c>0$ such that $R(3,n) > cn\sqrt{n}$ for every $n$.

for any $p\in (0,1)$ there exists a set of vertices $A\subset V$ such that the union of $A$ and the set of all vertices not joined to any vertex of $A$ contains at most $np+n(1-p)^{\delta +1}$ vertices;

there exists a set of vertices $D\subset V$ such that every vertex of $V\setminus D$ is joined by an edge to some vertex of $D$ and $\left|D\right|\leqslant n\dfrac {1+\ln (\delta +1)}{\delta +1}$.

If $\dbinom {k}{m}p^{\binom {m}{2}}+\dbinom {k}{n}(1-p)^{\binom {n}{2}} < 1$ for some $p\in (0,1)$, then $R(m,n) > k$ (here $R(m,n)$ are the Ramsey numbers, see Sec. 4.1).

$R(4,n) \geqslant \Omega \left(\dfrac {n^2}{\ln^2 n}\right)$ (we write $g \geqslant \Omega (f)$ if $f=O(g)$).

Cherchez la femme. At a Russian-French meeting there were no representatives of other countries. The total amount of money held by the French turned out to be greater than the total amount of money held by the Russians, and the total amount of money held by the women turned out to be greater than the total amount of money held by the men. Must there have been a Frenchwoman at the meeting?

Banknotes of different denominations and from different countries are packed into two suitcases. The average value of a banknote equals 100 rubles. The total number of banknotes in the left suitcase is greater than in the right one. Must there be a banknote worth at most 200 rubles in the left suitcase? (Cf. Markov's inequality 6.3.9 (1).)

For any integers $l,q>0$ there exists a graph that contains no cycles of length less than $l$ and cannot be properly colored in $q$ colors. (See the definition of a proper coloring in Sec. 3.1.)

isolated vertices;

triangles;

$k$-cliques;

$k$-cliques that are connected components;

Hamiltonian cycles;

non-self-intersecting cycles of length $k$;

non-self-intersecting cycles of length $k$ that are connected components with exactly $k$ edges;

trees with $k$ vertices;

tree components of a given size $k$, i.e., trees with $k$ vertices that are connected components.

isolated vertices;

triangles.

$\mathbb {E}\left[X+Y\right] = \mathbb {E}\left[X\right]+\mathbb {E}\left[Y\right]$;

$\operatorname {Var}\left[X+Y\right] = \operatorname {Var}\left[X\right]+\operatorname {Var}\left[Y\right]$ if $X$ and $Y$ are independent (i.e., for any $x,y$ we have $\mathbb {P}\left(X=x,Y=y\right)=\mathbb {P}\left(X=x\right)\cdot \mathbb {P}\left(Y=y\right)$).

Markov’s inequality. $\mathbb {P}\left(\left|X\right|>a\right) \leqslant \mathbb {E}\left[\left|X\right|\right]/a$. (Cf. Problem 6.3.3 (1).)

Chebyshev’s inequality. $\mathbb {P}\left(\left|X-\mathbb {E}\left[X\right]\right|>a\right) \leqslant \operatorname {Var}\left[X\right]/a^2$.

a.a.s.there are more than $n/2$ isolated vertices;

for some $C>0$, a.a.s.every connected component has fewer than $C\ln n$ vertices (specialists say: fewer than $O(\ln n)$ vertices);

a.a.s.every connected component is a tree or a unicyclic graph;

for some $C>0$, a.a.s.there are fewer than $C$ unicyclic components.

For $p(n)=o(n^{-3/2})$, a.a.s.the edges are pairwise disjoint.

For $p=p(n)=o(n^{-3/2})$ and $pn^2\to \infty$, there exists a function $r=r(n)=o(pn^2)$ such that a.a.s.the number of vertices of degree 1 is greater than $pn^2-r$ and less than $pn^2+r$, and the degrees of all the other vertices are zero.