Journal
JOURNAL OF COMBINATORIAL THEORY SERIES B
Volume 158, Issue -, Pages 264-285Publisher
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.jctb.2022.10.003
Keywords
Ramsey number; Size-Ramsey number; Cycle; Random graph; Expanders
Categories
Ask authors/readers for more resources
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.
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available