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 σn? An old argument of Shamir and Spencer gives an upper bound of O(√n), improved by a logarithmic factor by Alon. For general n, a result with Annika Heckel implies that n1/2 is tight up to log factors. However, according to the 'zig-zag' conjecture σn is expected to vary between n1/4+o(1) and n1/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∗(n1/3) upper bound for certain values of n, the first bound beating n1/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).