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/2o(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).
Last updated on 16 Feb 2025, 10:23pm. Please contact us with feedback and comments about this page.