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

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