Past exam of the mathematics course of the University of Cambridge / 2015 / ii / Paper 2 / 14I / b / Solution

Induction with Pascal's identity gives the binomial upper bound for a Ramsey number $R(s,t)\le \left(\genfrac{}{}{0ex}{}{s+t-2}{s-1}\right)$. Thus $R(s)\le \left(\genfrac{}{}{0ex}{}{2s-2}{s-1}\right)\le 4^{s-1}$, proving $R(s)=O(4^s)$.

For the lower bound, take a binomial random graph $G(n,1/2)$. The expected total number of $s$-cliques and independent $s$-sets isFor $n=\lfloor 2^{s/2}/2\rfloor$, this is at most $2^{1-s/2}/s!<1$ for all sufficiently large $s$. Some graph therefore has neither forbidden set, so $R(s)>n$. This proves $R(s)=\Omega (2^{s/2})$ by the probabilistic method.