go-v.orgdoi

On the Concentration of the Chromatic Number of Random Graphs

Erlang Surya, Lutz Warnke · The Electronic Journal of Combinatorics · 2024

  • DOI 10.37236/11638
  • Publisher Electronic Journal of Combinatorics
  • Type article
  • Issued 2024

Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.

The Electronic Journal of Combinatorics · Electronic Journal of Combinatorics · article · 2024

Abstract

Shamir and Spencer proved in the 1980s that the chromatic number of the binomial random graph $G_{n,p}$ is concentrated in an interval of length at most $\omega\sqrt{n}$, and in the 1990s Alon showed that an interval of length $\omega\sqrt{n}/\log n$ suffices for constant edge-probabilities $p\in (0,1)$. We prove a similar logarithmic improvement of the Shamir-Spencer concentration results for the sparse case ${p=p(n) \to 0}$, and uncover a surprising concentration `jump' of the chromatic number in the very dense case ${p=p(n) \to 1}$.

Open the resolved locator · 10.37236/11638

Metadata licence: OpenAlex metadata (CC0)