On the concentration of the chromatic number of random graphs

Authors: Erlang Surya, Lutz Warnke

12 pages, 1 figure

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.

Submitted to arXiv on 03 Jan. 2022

Explore the paper tree

Click on the tree nodes to be redirected to a given paper and access their summaries and virtual assistant

Also access our AI generated Summaries, or ask questions about this paper to our AI assistant.

Look for similar papers (in beta version)

By clicking on the button above, our algorithm will scan all papers in our database to find the closest based on the contents of the full papers and not just on metadata. Please note that it only works for papers that we have generated summaries for and you can rerun it from time to time to get a more accurate result while our database grows.