Suppose aliens invade the earth and threaten to obliterate it in a year’s time unless human beings can find the Ramsey number for red five and blue five. We could marshal the world’s best minds and fastest computers, and within a year we could probably calculate the value. If the aliens demanded the Ramsey number for red six and blue six, however, we would have no choice but to launch a preemptive attack.-Paul Erdős

Ramsey numbers:

The Ramsey number \(R(s,n)\) is the smallest integer \(N\) such that every red-blue coloring of the edges of a complete graph \(K_N\) on \(N\) vertices contains a red clique of size \(s\) or a blue clique of size \(n\).

Erdős-Ramsey theorem:

\(R(\alpha,\alpha) > n\) for all \(n\) and \(\alpha\) satisfying:

\begin{equation} {n \choose \alpha} \cdot 2^{1-{\alpha \choose 2}} < 1 \end{equation}

so for any \(n\) that satisfies this inequality, we can color \(K_n\) with no monochromatic \(K_{\alpha}\).

Proof:

Let’s suppose we randomly color the edges of \(K_n\) so any edge is red or blue with equal probability, \(p= \frac{1}{2}\).

Given any set \(R\) of \(\alpha\) vertices, let \(A_R\) be the event where \(R\) is monochromatic so all \({\alpha \choose 2}\) edges are the same color. As there are only two ways to color \(R\), the probability that \(A_R\) occurs for any given \(R\) is:

\begin{equation} 2 \cdot 2^{-{\alpha \choose 2}} \end{equation}

and so the event that \(K_n\) contains a monochromatic \(K_{\alpha}\) is:

\begin{equation} P\big(\bigcup_{R} A_R \big) = 1 \end{equation}

where \(R \in {[1,n] \choose \alpha}\).

Now, if we apply the union bound we find:

\begin{equation} P\big(\bigcup_{R} A_R \big) \leq \sum_R P(A_R) = {n \choose \alpha} \cdot 2^{1-{\alpha \choose 2}} \end{equation}

so we may deduce that:

\begin{equation} {n \choose \alpha} \cdot 2^{1-{\alpha \choose 2}} < 1 \implies R(\alpha,\alpha) > n \end{equation}

as this implies that \(K_n\) has a two-coloring such that no sub-clique \(K_{\alpha}\) is monochromatic.