“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 16040
School of Mathematics
  Title:   On the size-Ramsey number of cycles
  Author(s):  Gholam Reza Omidi (Joint with R. Javadi, F. Khoeini, and A. Pokrovskiy)
  Status:   Published
  Journal: Combin. Probab. Comput.
  Vol.:  28
  Year:  2019
  Pages:   871-880
  Supported by:  IPM
For given graphs G1,... , Gk, the size-Ramsey number is the smallest integer m for which there exists a graph H on m edges such that in every k-edge colouring of H with colours 1,... ,k, H contains a monochromatic copy of Gi of colour i for some 1 �?� i �?� k. We denote by when G1 = �?� = Gk = G. Haxell, Kohayakawa and Łuczak showed that the size-Ramsey number of a cycle Cn is linear in n, for some constant ck. Their proof, however, is based on Szemerédi's regularity lemma so no specific constant ck is known. In this paper, we give various upper bounds for the size-Ramsey numbers of cycles. We provide an alternative proof of , avoiding use of the regularity lemma, where ck is exponential and doubly exponential in k, when n is even and odd, respectively. In particular, we show that for sufficiently large n we have , where c = 6.5 if n is even and c = 1989 otherwise.

Download TeX format
back to top
scroll left or right