Anti-concentration of the chromatic number of a dense random graph

Primarily AI-generated textHuman understanding: no partsmath.CO — Combinatorics

Contributed by Will Howe, Grant Huffman, Jensen Kohlmeyer, Liam Kruer ↗

Version 1 / Nov 18, 2026 / CC BY 4.0

Abstract

For Gn∼G(n,1/2)G_n\sim G(n,1/2) and each fixed 0<d<1/40<d<1/4, we obtain that the supremum over intervals of radius ndn^d of the probability that χ(Gn)\chi(G_n) 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

AI tools assisted with developing and checking arguments and with drafting this manuscript.

References

  1. T. F. Bloom, Erdős Problem #1156 , https://www.erdosproblems.com/1156.link
  2. A. Heckel, Non-concentration of the chromatic number of a random graph , arXiv:1906.11808 (https://arxiv.org/abs/1906.11808).arXiv
  3. A. Heckel and K. Panagiotou, Colouring random graphs: Tame colourings , arXiv:2306.07253v3 (https://arxiv.org/abs/2306.07253v3), 2024.arXiv
  4. 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

  1. v1 · 16 pagesSubmitted by Liam KruerInitial depositCurrentNov 18, 2026