Cube-root concentration of the chromatic number of $G(n,1/2)$ – sometimes

Seminar series

Combinatorial Theory Seminar

Date

Tue, 18 Feb 2025

Time

14:00 - 15:00

Location

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)$ .