Abstract

Let $G(n,1/2)$ be the random graph on $n$ vertices in which each edge is present with probability $1/2$, independently of the others. A classical question is: what is the chromatic number $X_n$ of $G(n,1/2)$, i.e., how many colours do we need to colour all vertices so that adjacent vertices receive different colours? Of course, $X_n$ is a random variable: one main thrust of past work is proving better and better upper and lower bounds that hold with high probability (probability tending to 1), starting with the asymptotic formula proved by Bollob\’as in the 1980s. A separate direction asked: even if we can’t pin down the value of $X_n$ precisely, can we bound how much it varies? A nowadays standard argument gives an upper bound of $O(n^{1/2})$. Surprisingly, until very recently \emph{no} meaningful lower bounds were known, although this natural question was raised by Bollob\’as many years ago. Recently, Annika Heckel made a breakthrough, establishing a lower bound of $n^{1/4-o(1)}$. She and I have now extended this to $n^{1/2-o(1)}$, almost matching the upper bound.