## “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
Author(s):
 1 Ramin Javadi 2 Meysam Miralaei
Status:   Published
Journal: J. Combin. Theory Ser. B
Vol.:  158
Year:  2023
Pages:   264-285
Supported by:  IPM
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$.\\