{
  "id": "2207.02920",
  "version": "v1",
  "published": "2022-07-06T18:57:28.000Z",
  "updated": "2022-07-06T18:57:28.000Z",
  "title": "The Erdős-Gyárfás function $f(n, 4, 5) = \\frac 56 n + o(n)$ -- so Gyárfás was right",
  "authors": [
    "Patrick Bennett",
    "Ryan Cushman",
    "Andrzej Dudek",
    "Paweł Prałat"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "A $(4, 5)$-coloring of $K_n$ is an edge-coloring of $K_n$ where every $4$-clique spans at least five colors. We show that there exist $(4, 5)$-colorings of $K_n$ using $\\frac 56 n + o(n)$ colors. This settles a disagreement between Erd\\H{o}s and Gy\\'arf\\'as reported in their 1997 paper. Our construction uses a randomized process which we analyze using the so-called differential equation method to establish dynamic concentration. In particular, our coloring process uses random triangle removal, a process first introduced by Bollob\\'as and Erd\\H{o}s, and analyzed by Bohman, Frieze and Lubetzky.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-07-06T18:57:28.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "erdős-gyárfás function",
      "differential equation method",
      "random triangle removal",
      "establish dynamic concentration",
      "clique spans"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}