{
  "id": "2106.16023",
  "version": "v1",
  "published": "2021-06-30T12:43:32.000Z",
  "updated": "2021-06-30T12:43:32.000Z",
  "title": "Multicolor Size-Ramsey Number of Cycles",
  "authors": [
    "Ramin Javadi",
    "Meysam Miralaei"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Given a positive integer $ r $, the $ r $-color size-Ramsey number of a graph $ H $, denoted by $ \\hat{R}(H, r) $, is the smallest integer $ m $ for which there exists a graph $ G $ with $ m $ edges such that, in any edge coloring of $ G $ with $ r $ colors, $G$ contains a monochromatic copy of $ H $. Haxell, Kohayakawa and \\L uczak showed that the size-Ramsey number of a cycle $ C_n $ is linear in $ n $ i.e. $ \\hat{R}(C_n, r) \\leq c_rn $, for some constant $ c_r $. Their proof, however, is based on the Szemer\\'edi's regularity lemma and so no specific constant $ c_r $ is known. Javadi, Khoeini, Omidi and Pokrovskiy gave an alternative proof for this result which avoids using of the regularity lemma. Indeed, they proved that if $ n $ is even, then $ c_r $ is exponential in $ r $ and if $ n $ is odd, then $ c_r $ is doubly exponential in $ r $. \\noindent In this paper, we improve the bound $c_r$ and prove that $c_r$ is polynomial in $r$ when $n$ is even and is exponential in $r$ when $n$ is odd. We also prove that in the latter case, it cannot be improved to a polynomial bound in $r$. More precisely, we prove that there are some positive constants $c_1,c_2$ such that for every even integer $n$, we have $c_1r^2n\\leq \\hat{R}(C_n,r)\\leq c_2r^{120}(\\log^2 r)n$ and for every odd integer $n$, we have $c_1 2^{r}n \\leq \\hat{R}(C_n, r)\\leq c_22^{16 r^2+2\\log r}n $.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-06-30T12:43:32.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "multicolor size-ramsey number",
      "exponential",
      "szemeredis regularity lemma",
      "polynomial bound",
      "monochromatic copy"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}