“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 17011
School of Mathematics
  Title:   The multicolor size-Ramsey numbers of cycles
1.  Ramin Javadi
2.  Meysam Miralaei
  Status:   Published
  Journal: J. Combin. Theory Ser. B
  Vol.:  158
  Year:  2023
  Pages:   264-285
  Supported by:  IPM
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 $.\\

Download TeX format
back to top
scroll left or right