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}$.
@article{10_37236_11638,
author = {Erlang Surya and Lutz Warnke},
title = {On the concentration of the chromatic number of random graphs},
journal = {The electronic journal of combinatorics},
year = {2024},
volume = {31},
number = {1},
doi = {10.37236/11638},
zbl = {1540.05060},
url = {http://geodesic.mathdoc.fr/articles/10.37236/11638/}
}
TY - JOUR
AU - Erlang Surya
AU - Lutz Warnke
TI - On the concentration of the chromatic number of random graphs
JO - The electronic journal of combinatorics
PY - 2024
VL - 31
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/11638/
DO - 10.37236/11638
ID - 10_37236_11638
ER -
%0 Journal Article
%A Erlang Surya
%A Lutz Warnke
%T On the concentration of the chromatic number of random graphs
%J The electronic journal of combinatorics
%D 2024
%V 31
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/11638/
%R 10.37236/11638
%F 10_37236_11638
Erlang Surya; Lutz Warnke. On the concentration of the chromatic number of random graphs. The electronic journal of combinatorics, Tome 31 (2024) no. 1. doi: 10.37236/11638
