Exercise 1973Combinatorics › Graph theoryOlympiadAdded 5 Nov 2026

Erdős's lower bound for Ramsey numbers

#probabilistic method#Ramsey theory#expectation

Statement

Let $k\ge3$ and $n=\lfloor2^{k/2}\rfloor$ . Prove that the edges of the complete graph $K_n$ can be coloured with two colours without creating a monochromatic $K_k$ . For example, $k=10$ gives a colouring of $K_{32}$ with no monochromatic $K_{10}$ .

Hint

Colour every edge red or blue at random with probability $\frac12$ . Compute the expected number of monochromatic $k$ -subsets and show it is below $1$ .

Show solutionHide solution

Solution

Idea. If the expected number of bad sets is below $1$ , some colouring has none.

Expectation. A fixed set of $k$ vertices has $\binom k2$ edges and is monochromatic with probability $2\cdot2^{-\binom k2}$ . By linearity of expectation, the expected number of monochromatic $k$ -sets is
$E=\binom nk2^{1-\binom k2}.$

Estimate. Using $\binom nk\le\dfrac{n^k}{k!}\le\dfrac{2^{k^2/2}}{k!}$ ,
$E\le\frac{2^{k^2/2}}{k!}\cdot2^{1-\frac{k(k-1)}2}=\frac{2^{1+k/2}}{k!}.$
For $k=3$ this is $\frac{2^{2.5}}6\approx0.94<1$ ; for $k\ge4$ it stays below $1$ .

Conclusion. Since $E<1$ , there is a colouring in which the number of monochromatic $k$ -sets is $0$ . ∎

Lesson. Probabilistic method: show existence by exhibiting a random object whose expected number of defects is less than $1$ .

Erdős's lower bound for Ramsey numbers

Statement

Solution

More problems in Graph theory