On the size-Ramsey number of cycles

Abstract

For given graphs $G_1,\dots ,G_k$, the size-Ramsey number $\hat{R}(G_1,\dots ,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,\dots ,k$, $H$ contains a monochromatic copy of $G_i$ of color $i$ for some $1\le i\le k$. We denote $\hat{R}(G_1,\dots ,G_k)$ by ${\hat{R}}_k(G)$ when $G_1=\cdots =G_k=G$. Haxell, Kohayakawa and Łuczak showed that the size Ramsey number of a cycle $C_n$ is linear in $n$ i.e. ${\hat{R}}_k(C_n)\le c_{k}n$ for some constant $c_k$. Their proof, is based on the regularity lemma of Szemeré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)\le 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)\le 10^6\times cn,$ where $c=843$ if $n$ is even and $c=113482$ otherwise.