There are many impressive results asserting that the chromatic number of a random graph is sharply concentrated. In 1987, Shamir and Spencer showed that for any function $p=p(n)$, the chromatic number of $G(n,p)$ is concentrated on at most about $n^{1/2}$ consecutive values. For sparse random graphs with $p<n^{-1/2-\epsilon}$, much sharper concentration is known to hold: Alon and Krivelevich showed that in this case, the chromatic number of $G(n,p)$ is concentrated on only two consecutive values.

However, until recently there had been no non-trivial cases where the chromatic number was known not to be extremely narrowly concentrated. In 1992, Erdős asked whether the chromatic number of $G(n, 1/2)$ can be shown not to be concentrated on constantly many values. In 2004, Bollobás asked for any non-trivial results asserting a lack of concentration, noting that even the weakest such results would be of interest.

In this talk, we show that the chromatic number of $G(n, 1/2)$ is not concentrated on any sequence of intervals of length $n^{1/2-\epsilon}$ for any constant $\epsilon>0$. Up to the $\epsilon$, this exponent matches the upper bound from the classic result of Shamir and Spencer.

Joint work with Oliver Riordan.