{"id":"arxiv/2610.35003","url":"https://arxiv.org/abs/2610.35003","tags":["math.CO"],"score":0,"title":"The Choice Number of Random Graphs","domain":"math.CO","source":"arxiv","authors":["Lanchao Wang","Jiasheng Zeng"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-26","reactions":{}}