The multicolor size-Ramsey numbers of cycles

Given a positive integer r, the r -color size-Ramsey number of a graph H, denoted by circumflex accent R(H, r), is the smallest number of edges in a graph G such that in any edge coloring of G with r colors, G contains a monochromatic copy of H. Haxell, Kohayakawa , Luczak showed that the size-Ramsey number of a cycle Cn is linear in n i.e. circumflex accent R(Cn, r) <= f(r)n, for some function f (r). Their proof, however, is based on the Szemeredi's regularity lemma and no explicit function f (r) is given there. Javadi, Khoeini, Omidi and Pokrovskiy gave an alternative proof for this result which avoids using the regularity lemma. Indeed, they proved that f (r) can be taken to be exponential and doubly exponential in r, in case n is even and odd, respectively.In this paper, we improve the upper bound f (r) to a polynomial function in r when n is even and to an exponential function 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, c' such that for every even integer n, we have c r2n < circumflex accent R(Cn, r) < c'r120(log2r)n , for every odd integer n, we have c2rn < circumflex accent R(Cn, r) < ci r2216r2n.(c) 2022 Elsevier Inc. All rights reserved.

Automated summary

Given a positive integer r, the r-color size-Ramsey number of a graph H, denoted by circumflex accent R(H, r), is the smallest number of edges in a graph G such that in any edge coloring of G with r colors, G contains a monochromatic copy of H. We improve the upper bound of f(r) to a polynomial function in r when n is even and to an exponential function in r when n is odd. It is also proved that in the latter case, it cannot be improved to a polynomial bound in r.