Multicolour Ramsey Numbers of Odd Cycles

Abstract

We show that for any positive integer $r$ there exists an integer $k$ and a $k$-colouring of the edges of $K_{2^k+1}$ with no monochromatic odd cycle of length less than $r$. This makes progress on a problem of Erdős and Graham and answers a question of Chung. We use these colourings to give new lower bounds on the $k$-colour Ramsey number of the odd cycle and prove that, for all odd $r$ and all $k$ sufficiently large, there exists a constant $\epsilon =\epsilon (r)>0$ such that $R_k(C_r)>(r-1)(2+\epsilon {)}^{k-1}$.