Probabilistic method

$\left|\sum_{k=1}^{n}\varepsilon_kv_k\right| \leqslant \sqrt{n}$,

$\left|\sum_{k=1}^{n}\varepsilon_kv_k\right| \geqslant \sqrt{n}$.

If for some even $n$

then in an $n$-element set one can find $l$ subsets of $k$ elements each such that for any coloring of the elements of this set in two colors at least one of these $l$ subsets is monochromatic.

There exists $c>0$ such that for any $k$ there exist $k$-element subsets of some set, at most $ck^22^k$ in number, such that for any coloring of the elements of this set in two colors one of these subsets is monochromatic.

$R(n, n) > (n-1)^2$.

Erdős’s theorem. $R(n, n) > n2^{(n-3)/2}$ for all sufficiently large $n$. (More precisely, Erdős's theorem states that $R(n, n) \gtrsim n2^{n/2}/e$. The symbol $\gtrsim$ is defined in Sec. 6.1.)

If $\binom {r}{n} < 2^{\binom {n}{2}-1}$, then $R(n, n) > r$.

If $\binom {r}{n} < s2^{\binom {n}{2}-1}$, then $R(n, n) > r - s$.

$R(n, n) > r - \binom {r}{n}2^{1-\binom {n}{2}}$ for every $r$.

4.1.5(1);

4.1.5(2).

If $\binom {r}{n} < 2^{\binom {n}{3}-1}$, then $R_3(n, n) > r$.

There exists a number $c > 0$ such that $R_3(n, n) \geqslant 2^{cn^2}$.

Find lower bounds on $R_l(\underbrace{n, \ldots , n}_{k})$ analogous to Statements 4.1.5(1, 2) (cf. Problem 4.2.7).

For any $(n,s,k)$-collection there exists an SCR of size less than

If $n \geqslant 32k$ and $60 \leqslant \dfrac {sk}{n} < e^{k}$, then there exists an $(n,s,k)$-collection every SCR of which has size greater than $\dfrac {n}{64k}\ln \dfrac {sk}{n}$.

If

then there exists an $(n,s,k)$-collection every SCR of which has size greater than $l$.

For all sufficiently large $n$, if $k^{2}l+kl^{2} < n^{1{,}8}$, then $k < n-l$ and $\binom {n}{k}\Big/\binom {n-l}{k} < 2e^{kl/n}$.

For all sufficiently large $n$ and $k$, if $101\ln \ln k < \ln \dfrac {sk}{n} < \sqrt{k} < \sqrt[4]{n}$, then there exists an $(n,s,k)$-collection every SCR of which has size greater than $0{,}99\dfrac {n}{k}\ln \dfrac {sk}{n}$.

If

then there exists an $(n,s,k)$-collection every SCR of which has size greater than $l$.

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.

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.)