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:

$${n \choose \alpha} \cdot 2^{1-{\alpha \choose 2}} < 1$$

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:

$$2 \cdot 2^{-{\alpha \choose 2}}$$

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

$$P\big(\bigcup_{R} A_R \big) = 1$$

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

Now, if we apply the union bound we find:

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

so we may deduce that:

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

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