= Solution
Throughout this question the <binomial random graph> has $p=1/2$, as fixed in the introduction. Let $L=\log_2n$ and $s=\lceil2L\rceil$. Count the $s$-vertex <independent sets> by a <random variable> $I_s$. <Linearity of expectation> gives
$$
\mathbb EI_s=\binom ns2^{-\binom s2}
\leq\frac{n^s2^{-s(s-1)/2}}{s!}
\leq\frac{\sqrt2\,n}{s!}=o(1).
$$
For the second inequality, $s\geq2L$ implies $sL-s(s-1)/2\leq s/2\leq L+1/2$. For the limit, $s!\geq(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)\leq s-1<2L$ <with high probability>.
Every class of a proper <graph coloring> is an <independent set>, giving \b[the claimed chromatic lower bound]:
$$
\boxed{\chi(G)\geq\frac n{\alpha(G)}\geq\frac n{2\log_2n}\quad\text{with high probability}.}
$$
Back to article page
