{
  "id": "1508.03870",
  "version": "v1",
  "published": "2015-08-16T21:52:36.000Z",
  "updated": "2015-08-16T21:52:36.000Z",
  "title": "Chromatic thresholds in dense random graphs",
  "authors": [
    "Peter Allen",
    "Julia Böttcher",
    "Simon Griffiths",
    "Yoshiharu Kohayakawa",
    "Robert Morris"
  ],
  "comment": "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",
  "categories": [
    "math.CO"
  ],
  "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\\H{o}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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-08-16T21:52:36.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "dense random graphs",
      "chromatic threshold",
      "sparser random graphs",
      "significant progress",
      "high probability"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 36,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv150803870A"
    }
  }
}