{
  "id": "1203.2259",
  "version": "v1",
  "published": "2012-03-10T16:24:41.000Z",
  "updated": "2012-03-10T16:24:41.000Z",
  "title": "Cycles are strongly Ramsey-unsaturated",
  "authors": [
    "Jozef Skokan",
    "Maya Stein"
  ],
  "doi": "10.1017/S0963548314000212",
  "categories": [
    "math.CO"
  ],
  "abstract": "We call a graph H Ramsey-unsaturated if there is an edge in the complement of H such that the Ramsey number r(H) of H does not change upon adding it to H. This notion was introduced by Balister, Lehel and Schelp who also proved that cycles (except for $C_4$) are Ramsey-unsaturated, and conjectured that, moreover, one may add any chord without changing the Ramsey number of the cycle $C_n$, unless n is even and adding the chord creates an odd cycle. We prove this conjecture for large cycles by showing a stronger statement: If a graph H is obtained by adding a linear number of chords to a cycle $C_n$, then $r(H)=r(C_n)$, as long as the maximum degree of H is bounded, H is either bipartite (for even n) or almost bipartite (for odd n), and n is large. This motivates us to call cycles strongly Ramsey-unsaturated. Our proof uses the regularity method.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2012-03-10T16:24:41.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C55"
    ],
    "keywords": [
      "ramsey number",
      "maximum degree",
      "linear number",
      "stronger statement"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1203.2259S"
    }
  }
}