“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
Paper IPM / M / 16040  


Abstract:  
For given graphs G1,... , Gk, the sizeRamsey number is the smallest integer m for which there exists a graph H on m edges such that in every kedge 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 sizeRamsey 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 sizeRamsey 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 