{
  "id": "1208.1732",
  "version": "v2",
  "published": "2012-08-08T18:40:22.000Z",
  "updated": "2013-12-13T15:22:08.000Z",
  "title": "Ramsey numbers of cubes versus cliques",
  "authors": [
    "David Conlon",
    "Jacob Fox",
    "Choongbum Lee",
    "Benny Sudakov"
  ],
  "comment": "26 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "The cube graph Q_n is the skeleton of the n-dimensional cube. It is an n-regular graph on 2^n vertices. The Ramsey number r(Q_n, K_s) is the minimum N such that every graph of order N contains the cube graph Q_n or an independent set of order s. Burr and Erdos in 1983 asked whether the simple lower bound r(Q_n, K_s) >= (s-1)(2^n - 1)+1 is tight for s fixed and n sufficiently large. We make progress on this problem, obtaining the first upper bound which is within a constant factor of the lower bound.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2013-12-13T15:22:08.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C55",
      "05D10"
    ],
    "keywords": [
      "ramsey number",
      "cube graph",
      "simple lower bound",
      "first upper bound",
      "n-dimensional cube"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 26,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1208.1732C"
    }
  }
}