Seminar series
Date
Tue, 18 Feb 2025
Time
14:00 -
15:00
Location
L4
Speaker
Oliver Riordan
Organisation
University of Oxford
A classical question in the theory of random graphs is 'how much does the chromatic number of $G(n,1/2)$ vary?' For example, roughly what is its standard deviation $\sigma_n$? An old argument of Shamir and Spencer gives an upper bound of $O(\sqrt{n})$, improved by a logarithmic factor by Alon. For general $n$, a result with Annika Heckel implies that $n^{1/2}$ is tight up to log factors. However, according to the 'zig-zag' conjecture $\sigma_n$ is expected to vary between $n^{1/4+o(1)}$ and $n^{1/2+o(1)}$ as $n$ varies. I will describe recent work with Rob Morris, building on work of Bollobás, Morris and Smith, giving an $O^*(n^{1/3})$ upper bound for certain values of $n$, the first bound beating $n^{1/2-o(1)}$, and almost matching the zig-zag conjecture for these $n$. The proof uses martingale methods, the entropy approach of Johansson, Kahn and Vu, the second moment method, and a new (we believe) way of thinking about the distribution of the independent sets in $G(n,1/2)$.