Chromatic thresholds in dense random graphs

Abstract

The chromatic threshold ${\delta }_{\chi }(H,p)$ of a graph $H$ with respect to the random graph $G(n,p)$ is the infimum over $d>0$ such that the following holds with high probability: the family of $H$-free graphs $G\subset G(n,p)$ with minimum degree $\delta (G)\ge dpn$ has bounded chromatic number. The study of the parameter ${\delta }_{\chi }(H):={\delta }_{\chi }(H,1)$ was initiated in 1973 by Erdős and Simonovits, and was recently determined for all graphs $H$. In this paper we show that ${\delta }_{\chi }(H,p)={\delta }_{\chi }(H)$ for all fixed $p\in (0,1)$, but that typically ${\delta }_{\chi }(H,p)\ne {\delta }_{\chi }(H)$ if $p=o(1)$. We also make significant progress towards determining ${\delta }_{\chi }(H,p)$ for all graphs $H$ in the range $p=n^{-o(1)}$. In sparser random graphs the problem is somewhat more complicated, and is studied in a separate paper.

36 pages (including appendix), 1 figure; the appendix is copied with minor modifications from arXiv:1108.1746 for a self-contained proof of a technical lemma; accepted to Random Structures and Algorithms