A canonical Ramsey theorem for even cycles in random graphs

Abstract

The celebrated canonical Ramsey theorem of Erdős and Rado implies that for $2\le k\in \mathbb{N}$, any colouring of the edges of $K_n$ with $n$ sufficiently large gives a copy of $C_{2k}$ which has one of three canonical colour patterns: monochromatic, rainbow or lexicographic. In this paper we show that if $p=\ddot{I}‰(n^{-1+1/(2k-1)}\log n)$, then $\mathbf{G}(n,p)$ will asymptotically almost surely also have the property that any colouring of its edges induces canonical copies of $C_{2k}$. This determines the threshold for the canonical Ramsey property with respect to even cycles, up to a $\log$ factor.

25 pages + 4 pages of appendix, 1 figure. Final version, to appear in CPC