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.

Please contact us with feedback and comments about this page. Last updated on 03 Apr 2022 01:32.