{
  "id": "1701.07348",
  "version": "v1",
  "published": "2017-01-25T15:13:15.000Z",
  "updated": "2017-01-25T15:13:15.000Z",
  "title": "On the size-Ramsey number of cycles",
  "authors": [
    "Ramin Javadi",
    "Farideh Khoeini",
    "Gholam Reza Omidi",
    "Alexey Pokrovskiy"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "For given graphs $G_1,\\ldots,G_k$, the size-Ramsey number $\\hat{R}(G_1,\\ldots,G_k)$ is the smallest integer $m$ for which there exists a graph $H$ on $m$ edges such that in every $k$-edge coloring of $H$ with colors $1,\\ldots,k$, $ H $ contains a monochromatic copy of $G_i$ of color $i$ for some $1\\leq i\\leq k$. We denote $\\hat{R}(G_1,\\ldots,G_k)$ by $\\hat{R}_{k}(G)$ when $G_1=\\cdots=G_k=G$. Haxell, Kohayakawa and \\L{}uczak showed that the size Ramsey number of a cycle $C_n$ is linear in $n$ i.e. $\\hat{R}_{k}(C_{n})\\leq c_k n$ for some constant $c_k$. Their proof, is based on the regularity lemma of Szemer\\'{e}di and so no specific constant $c_k$ is known. In this paper, we give various upper bounds for the size-Ramsey numbers of cycles. We give an alternative proof of $\\hat{R}_{k}(C_{n})\\leq c_k n$, avoiding the use of the regularity lemma. For two colours, we show that for sufficiently large $n$ we have $\\hat{R}(C_{n},C_{n}) \\leq 10^6\\times cn,$ where $c=843$ if $n$ is even and $c=113482$ otherwise.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-01-25T15:13:15.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C55",
      "05D10"
    ],
    "keywords": [
      "size-ramsey number",
      "regularity lemma",
      "upper bounds",
      "size ramsey number",
      "smallest integer"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}