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 < n^{-1/2-\varepsilon}$.

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 by 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.

combinatoricsprobability

Audience: researchers in the topic

Extremal and probabilistic combinatorics webinar

Series comments: We've added a password: concatenate the 6 first prime numbers (hence obtaining an 8-digit password).