“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
| Paper IPM / M / 17011 | ||||||||||||||||||||||
|
||||||||||||||||||||||
| Abstract: | ||||||||||||||||||||||
|
Given a positive integer r, the r-color size-Ramsey number of a graph H, denoted by ˆ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
Cn is linear in n i.e. ˆR(Cn,r)≤crn, for some constant cr. Their proof, however, is based on the Szemer\'edi's regularity lemma and so no specific constant cr 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 cr is exponential in r and if n is odd, then cr is doubly exponential in r.
\noindent
In this paper, we improve the bound cr and prove that cr 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 c1,c2 such that for every even integer n, we have c1r2n≤ˆR(Cn,r)≤c2r120(log2r)n and for every odd integer n, we have
c12rn≤ˆR(Cn,r)≤c2216r2+2logrn.\\
Download TeX format |
||||||||||||||||||||||
| back to top | ||||||||||||||||||||||
