Past exam of the mathematics course of the University of Cambridge / 2015 / ii / Paper 2 / 14I (Graph Theory)

The graph Ramsey number $R(s,t)$ is the least $N$ for which every graph on $N$ vertices has a clique of size $s$ or an independent set of size $t$; $R(s)=R(s,s)$ is the diagonal Ramsey number. The base cases are $R(2,t)=t$ and $R(s,2)=s$.

Assume the smaller parameters already have finite graph Ramsey numbers, and take $N=R(s-1,t)+R(s,t-1)$. For any vertex, either its neighbourhood has at least $R(s-1,t)$ vertices, or its nonneighbourhood has at least $R(s,t-1)$ vertices. In the first case it contains an independent $t$-set, or an $(s-1)$-clique which extends with the chosen vertex. In the second it contains an $s$-clique, or a $(t-1)$-independent set which extends with that vertex. Induction proves existence and

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.

The binomial upper bound for a Ramsey number gives $R(3,t)\le \left(\genfrac{}{}{0ex}{}{t+1}{2}\right)=O(t^2)$. For the triangle-free Ramsey lower bound by alteration, a binomial random graph $G(n,p)$ has expected triangle count $\left(\genfrac{}{}{0ex}{}{n}{3}\right)p^3$ and expected independent $t$-set count $\left(\genfrac{}{}{0ex}{}{n}{t}\right)(1-p{)}^{\left(\genfrac{}{}{0ex}{}{t}{2}\right)}$. Choose a realization whose sum of these counts is at most its expectation. Delete one vertex from each surviving forbidden set, iterating through the originally listed sets. The remaining graph has neither a triangle nor an independent $t$-set. This random alteration method provesFor large $t$, set $n=\lfloor (t/(4\log t){)}^{3/2}\rfloor$ and $p=n^{-2/3}$. The triangle term is at most $n/6$. Using $\left(\genfrac{}{}{0ex}{}{n}{t}\right)\le (en/t{)}^t$ and $1-p\le e^{-p}$, the logarithm of the independent-set term divided by $t$ is at mostwhich tends to $-\infty$. That term is eventually below $1$. Thus $R(3,t)>5n/6-1$ and