= Solution
Induction with Pascal's identity gives the <binomial upper bound for a Ramsey number> $R(s,t)\leq\binom{s+t-2}{s-1}$. Thus $R(s)\leq\binom{2s-2}{s-1}\leq4^{s-1}$, proving \b[$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 is
$$
2\binom ns2^{-\binom s2}\leq2\frac{n^s}{s!}2^{-s(s-1)/2}.
$$
For $n=\lfloor2^{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 \b[$R(s)=\Omega(2^{s/2})$] by the <probabilistic method>.
Back to article page
