Past exam of the mathematics course of the University of Cambridge / 2015 / iii / Paper 13 / 3 / i / Solution

Throughout this question the binomial random graph has $p=1/2$, as fixed in the introduction. Let $L={\log }_{2}n$ and $s=\lceil 2L\rceil$. Count the $s$-vertex independent sets by a random variable $I_s$. Linearity of expectation givesFor the second inequality, $s\ge 2L$ implies $sL-s(s-1)/2\le s/2\le L+1/2$. For the limit, $s!\ge (s/2{)}^{\lfloor s/2\rfloor }$ grows faster than $n$. By the first moment method, with high probability there is no such independent set; any larger independent set would contain one. Thus the independence number satisfies $\alpha (G)\le s-1<2L$ with high probability.

Every class of a proper graph coloring is an independent set, giving the claimed chromatic lower bound: