Multicolor Size-Ramsey Number of Cycles

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 Łuczak showed that the size-Ramsey number of a cycle $C_n$ is linear in $n$ i.e. $\hat{R}(C_n,r)\le c_{r}n$, for some constant $c_r$. Their proof, however, is based on the Szemerédi'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_1{r}^{2}n\le \hat{R}(C_n,r)\le c_2{r}^{120}({\log }^{2}r)n$ and for every odd integer $n$, we have $c_1{2}^{r}n\le \hat{R}(C_n,r)\le c_2{2}^{16r^2+2\log r}n$.