= Chromatic number of a binomial random graph
{title2=$\mathbb E\chi(G(n,p))\sim n/(2\log_{1/(1-p)}n)$}
For a fixed probability strictly between zero and one, the largest independent set has leading size $2\log_{1/(1-p)}n$, giving a lower bound for colouring. The matching upper bound uses <independent sets in every large subset of a dense random graph>, then repeatedly colours and removes such sets. A sufficiently strong probability estimate makes the failure contribution negligible for the expectation.
Back to article page
