The Choice Number of Random Graphs

Source abstract

In 1999, Alon, Krivelevich and Sudakov conjectured that the choice number and chromatic number of the random graph $G(n,p)$ are asymptotically equal whenever $np\to\infty$. We prove their conjecture, showing that, with high probability, $$\operatorname{ch}(G(n,p))=(1+o(1))χ(G(n,p))$$ whenever $np\to\infty$. This improves the bound $\operatorname{ch}(G(n,p))\le(2+o(1))χ(G(n,p))$ for $np\to\infty$ and $p\le0.9$ obtained by Krivelevich and Vu in 2001. Our proof distinguishes two cases according to the size of independent sets. When independent sets of growing size are available, we establish a sharper uniform independent-set estimate that eliminates the factor-two loss in the bound of Krivelevich and Vu. When independent sets have bounded size, we establish a deterministic result showing that, under a suitable uniform independent-set condition, a proper colouring with bounded colour-class sizes yields an asymptotically matching upper bound on the choice number.