The Ramsey number of mixed-parity cycles I

Denote by $R(G_1, G_2, G_3)$ the minimum integer $N$ such that any three-colouring of the edges of the complete graph on $N$ vertices contains a monochromatic copy of a graph $G_i$ coloured with colour $i$ for some $i\in{1,2,3}$. In a series of three papers of which this is the first, we consider the case where $G_1, G_2$ and $G_3$ are cycles of mixed parity. Specifically, in this and the subsequent paper, we consider $R(C_n,C_m,C_{\ell})$, where $n$ and $m$ are even and $\ell$ is odd. Figaj and Łuczak determined an asymptotic result for this case, which we improve upon to give an exact result. We prove that for $n,m$ and $\ell$ sufficiently large $R(C_n,C_m,C_\ell)=\max\{2n+m-3, n+2m-3, \tfrac{1}{2} n +\tfrac{1}{2} m + \ell - 2\}$. In the case that the longest cycle is of even length, the proof in this paper is self-contained. However, in the case that the longest cycle is of odd length, we require an additional technical result, the proof of which makes up the majority of the subsequent paper.

No reviews yet.

No comments yet.