Annika Heckel, LMU Munich

Abstract

There are many impressive results asserting that the chromatic number of G(n,p) 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 of G(n,p) 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.