Non-concentration of the chromatic number

Abstract: 

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)$ takes one of at most about $n^{1/2}$ consecutive values whp. For sparse random graphs, much sharper concentration is known to hold: Alon and Krivelevich proved two point concentration whenever $p$ is less than $n^{-1/2-\epsilon}$.

However, until recently no non-trivial lower bounds for the concentration were known for any $p$, even though the question was raised prominently by Erdős in 1992 and Bollobás in 2004.

In this talk, we show that the chromatic number of $G(n,1/2)$ is not whp contained in any sequence of intervals of length $n^{1/2-o(1)}$, almost matching Shamir and Spencer's upper bound.

Joint work with Oliver Riordan.

This is a seminar of the Combinatorial Mathematics Society of Australasia.

To attend email cmsa-webinar@monash.edu with the subject 'subscribe' to receive zoom details. [You only need to subscribe once, not for future talks.]