{
  "id": "1303.2951",
  "version": "v1",
  "published": "2013-03-12T16:55:40.000Z",
  "updated": "2013-03-12T16:55:40.000Z",
  "title": "The Erdős-Hajnal conjecture for rainbow triangles",
  "authors": [
    "J. Fox",
    "A. Grinshpun",
    "J. Pach"
  ],
  "comment": "43 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "We prove that every 3-coloring of the edges of the complete graph on n vertices without a rainbow triangle contains a set of order Omega(n^{1/3}log^2 n) which uses at most two colors, and this bound is tight up to a constant factor. This verifies a conjecture of Hajnal which is a case of the multicolor generalization of the well-known Erd\\H{o}s-Hajnal conjecture. We further establish a generalization of this result. For fixed positive integers s and r with s at most r, we determine a constant c_{r,s} such that the following holds. Every r-coloring of the edges of the complete graph on n vertices without a rainbow triangle contains a set of order Omega(n^{r(r-1)/s(s-1)}(\\log n)^{c_{r,s}}) which uses at most s colors, and this bound is tight apart from the implied constant factor. The proof of the lower bound utilizes Gallai's classification of rainbow-triangle free edge-colorings of the complete graph, a new weighted extension of Ramsey's theorem, and a discrepancy inequality in edge-weighted graphs. The proof of the upper bound uses Erd\\H{o}s' lower bound on Ramsey numbers by considering lexicographic products of 2-edge-colorings of complete graphs without large monochromatic cliques.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-03-12T16:55:40.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05D10",
      "05C55",
      "05C35",
      "05C15"
    ],
    "keywords": [
      "complete graph",
      "erdős-hajnal conjecture",
      "rainbow triangle contains",
      "lower bound utilizes gallais classification",
      "constant factor"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 43,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1303.2951F"
    }
  }
}