“School of Physics”
Back to Papers HomeBack to Papers of School of Physics
| Paper IPM / P / 17011 |
|
||||
| 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 $.\\
Download TeX format |
|||||
| back to top | |||||
