{
  "id": "1702.06227",
  "version": "v1",
  "published": "2017-02-21T01:02:32.000Z",
  "updated": "2017-02-21T01:02:32.000Z",
  "title": "A $(5,5)$-coloring of $K_n$ with few colors",
  "authors": [
    "Alex Cameron",
    "Emily Heath"
  ],
  "comment": "20 pages, 4 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "For fixed integers $p$ and $q$, let $f(n,p,q)$ denote the minimum number of colors needed to color all of the edges of the complete graph $K_n$ such that no clique of $p$ vertices spans fewer than $q$ distinct colors. Any edge-coloring with this property is known as a $(p,q)$-coloring. We construct an explicit $(5,5)$-coloring that shows that $f(n,5,5) \\leq n^{1/3 + o(1)}$ as $n \\rightarrow \\infty$. This improves upon the best known probabilistic upper bound of $O\\left(n^{1/2}\\right)$ given by Erd\\H{o}s and Gy\\'{a}rf\\'{a}s, and comes close to matching the best known lower bound $\\Omega\\left(n^{1/3}\\right)$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-02-21T01:02:32.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "vertices spans fewer",
      "probabilistic upper bound",
      "distinct colors",
      "lower bound",
      "minimum number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 20,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}