“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
| Paper IPM / M / 16040 |
|
| Abstract: | |
|
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 | |
