Date
Tue, 04 May 2021
14:00
Location
Virtual
Speaker
Annika Heckel
Organisation
LMU München

How much does the chromatic number of the random graph $G(n, 1/2)$ vary? Shamir and Spencer proved that it is contained in some sequence of intervals of length about $n^{1/2}$. Alon improved this slightly to $n^{1/2} / \log n$. Until recently, however, no lower bounds on the fluctuations of the chromatic number of $G(n, 1/2)$ were known, even though the question was raised by Bollobás many years ago. I will talk about the main ideas needed to prove that, at least for infinitely many $n$, the chromatic number of $G(n, 1/2)$ is not concentrated on fewer than $n^{1/2-o(1)}$ consecutive values.
I will also discuss the Zigzag Conjecture, made recently by Bollobás, Heckel, Morris, Panagiotou, Riordan and Smith: this proposes that the correct concentration interval length 'zigzags' between $n^{1/4+o(1)}$ and $n^{1/2+o(1)}$, depending on $n$.
Joint work with Oliver Riordan.

Further Information

Part of the Oxford Discrete Maths and Probability Seminar, held via Zoom. Please see the seminar website for details.

Last updated on 3 Apr 2022, 1:32am. Please contact us with feedback and comments about this page.