Prove $R(t,t) \ge 2^{t/2}$ for all $t\ge 3$

Question

Prove $R(t,t) \ge 2^{t/2}$ for all $t\ge 3$. I'm thinking about using induction. Base case: R(3,3)=6, which works. Inductive Step: I claim $\frac{R(t+1,t+1)}{R(t,t)} \ge \sqrt{2}$, which is true because $R(t+1,t+1)$ is approximately $2R(t,t+1)$, but I cannot find a formal proof.

Answer 1

There is a famous argument of Erdos of this lower bound (essentially showing that even though by Ramsey's theorem the Ramsey numbers are finite, they have to grow at least exponentially) which is a classical example of the so-called "probabilistic method". It's a charming proof and a very general technique so I'll take the opportunity to write down the argument. Here's how it goes:

Start with a complete graph $K_n$ and consider all possible bicolorings of the edges, which forms a sample space of configurations $\Omega$. There are $\binom{n}{t}$ many $t$-cliques in $K_n$, so enumerate these and let $A_i \subset \Omega$ for $1 \leq i \leq \binom{n}{t}$ be the event that the $i$-th clique is monochromatic. Then $E = \bigcup A_i$ is the event that there is at least one monochromatic $t$-clique in $K_n$. Note that for any $i$, $\Bbb P(A_i) = 2 \cdot 2^{-\binom{t}{2}}$ since there are $\binom{t}{2}$ edges in $K_t$, and in the event it's monochromatic, they are either all red or all blue. Now by Boole's inequality,

$$\Bbb P(E) \leq \sum_i \Bbb P(A_i) = \binom{n}{t} 2^{1-\binom{t}{2}} = \frac{n(n-1)\cdots(n-t+1)}{t!}2^{1-\binom{t}{2}} < \frac{n^t}{t!} 2^{1 - t(t-1)/2}$$

If we set $n = 2^{t/2}$ (or $\lfloor 2^{t/2} \rfloor$) then this expression is less than $2^{1+t/2}/t!$ which is in turn less than $1$ for all $t \geq 3$. This implies $\Bbb P(E) < 1$, so with nonzero probability one can pick a bicoloring of the complete graph on $2^{t/2}$ vertices with no monochromatic $t$-clique. In particular there exists a configuration containing no monochromatic $t$-cliques, which forces $R(t) > 2^{t/2}$.