Georgia Institute of Technology College of Sciences

What can we say about the chromatic number \chi(G_{n,p}) of an n-vertex binomial random graph G_{n,p}? From a combinatorial perspective, it is natural to ask about the typical value of \chi(G_{n,p}), i.e., upper and lower bounds that are close to each other. From a probabilistic combinatorics perspective, it is also natural to ask about the concentration of \chi(G_{n,p}), i.e., how much this random variable varies. Among these two fundamental questions, significantly less is known about the concentration question that we shall discuss in this talk. In terms of previous work, in the 1980s Shamir and Spencer proved 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). In this talk, we prove a similar logarithmic improvement of the Shamir-Spencer concentration results for the sparse case p=p(n) \to 0, and also discuss several intriguing questions about the chromatic number \chi(G_{n,p}) that remain open. Based on joint work with Erlang Surya; see https://arxiv.org/abs/2201.00906