{
  "id": "0803.2375",
  "version": "v2",
  "published": "2008-03-16T22:56:43.000Z",
  "updated": "2008-04-06T02:48:05.000Z",
  "title": "Unavoidable patterns",
  "authors": [
    "Jacob Fox",
    "Benny Sudakov"
  ],
  "comment": "10 pages, corrected typos",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let \\mathcal{F}_k denote the family of 2-edge-colored complete graphs on 2k vertices in which one color forms either a clique of order k or two disjoint cliques of order k. Bollob\\'as conjectured that for every \\epsilon>0 and positive integer k there is an n(k,\\epsilon) such that every 2-edge-coloring of the complete graph of order n \\geq n(k,\\epsilon) which has at least \\epsilon {n \\choose 2} edges in each color contains a member of \\mathcal{F}_k. This conjecture was proved by Cutler and Mont\\'agh, who showed that n(k,\\epsilon)<4^{k/\\epsilon}. We give a much simpler proof of this conjecture which in addition shows that n(k,\\epsilon)<\\epsilon^{-ck} for some constant c. This bound is tight up to the constant factor in the exponent for all k and \\epsilon. We also discuss similar results for tournaments and hypergraphs.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2008-04-06T02:48:05.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C55",
      "05C20",
      "05D10"
    ],
    "keywords": [
      "unavoidable patterns",
      "complete graph",
      "conjecture",
      "color contains",
      "2k vertices"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 10,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2008arXiv0803.2375F"
    }
  }
}