Anti-concentration of the chromatic number of a dense random graph
Version 1 / Nov 18, 2026 / CC BY 4.0
Abstract
For and each fixed , we obtain that the supremum over intervals of radius of the probability that lies in the interval tends to zero. This implies the failure of concentration on any fixed number of possible values and gives the eventual strict half-mass bound asked for in Erdős Problem 1156. The proof treats different supplies of large independent sets by matching sums and by one- and two-count Gaussian comparisons.
Provenance statement
References
- T. F. Bloom, Erdős Problem #1156 , https://www.erdosproblems.com/1156.link
- A. Heckel, Non-concentration of the chromatic number of a random graph , arXiv:1906.11808 (https://arxiv.org/abs/1906.11808).arXiv
- A. Heckel and K. Panagiotou, Colouring random graphs: Tame colourings , arXiv:2306.07253v3 (https://arxiv.org/abs/2306.07253v3), 2024.arXiv
- A. Heckel and O. Riordan, How does the chromatic number of a random graph vary? , J. Lond. Math. Soc. (2) (2023). doi:10.1112/jlms.12794 (https://doi.org/10.1112/jlms.12794).DOI
Version history
- v1 · 16 pagesSubmitted by Liam KruerInitial depositCurrentNov 18, 2026