TAU Combinatorics Seminar

TAU Combinatorics Seminar 2020/21

When: Sunday, November 15, 10am Speaker: Annika Heckel, LMU Munich Title: Non-concentration of the chromatic number and the Zig-zag conjecture

Abstract:

There are many impressive results asserting that the chromatic number of the random graph $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)$ 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-\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 Bollobás and Erdős since the late 80s. 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 classic upper bound. I will also discuss and give evidence for a recent conjecture on the correct concentration interval length, which seems to depend on $n$.

Joint work with Oliver Riordan.