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 n1/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 - \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.

discrete mathematicscombinatoricsprobability

Audience: researchers in the topic

Australasian Combinatorics Seminar

Series comments: Please note that we vary between 5pm and 11am (AEST) time slots