Chromatic thresholds in dense random graphs

Peter Allen, Julia Böttcher, Simon Griffiths, Yoshiharu Kohayakawa and Robert Morris

The chromatic threshold δχ(H, p) of a graph H with respect to the random graphG(n, p) is the infimum over d > 0 such that the following holds with high probability: the familyof H-free graphs G ⊆ G(n, p) with minimum degree δ(G) ≥ dpn has bounded chromatic number.The study of the parameter δχ(H) := δχ(H,1) was initiated in 1973 by Erd˝os and Simonovits, andwas recently determined for all graphs H. In this paper we show that δχ(H, p) = δχ(H) for all fixedp ∈ (0, 1), but that typically δχ(H, p) ≠ δχ(H) if p = o(1). We also make significant progress towardsdetermining δχ(H, p) for all graphs H in the range p = n−o(1). In sparser random graphs the problem issomewhat more complicated, and is studied in a separate paper.

The whole paper is available here.

NeuroCineMat
Featuring this week:
Newsletter

Stay informed on our latest news!



Previous issues

Podcast A Matemática do Cérebro
Podcast A Matemática do Cérebro
NeuroMat Brachial Plexus Injury Initiative
Logo of the NeuroMat Brachial Plexus Injury Initiative
Neuroscience Experiments System
Logo of the Neuroscience Experiments System
NeuroMat Parkinson Network
Logo of the NeuroMat Parkinson Network
NeuroMat's scientific-dissemination blog
Logo of the NeuroMat's scientific-dissemination blog