A canonical Ramsey theorem for even cycles in random graphs

Abstract

The celebrated canonical Ramsey theorem of Erdős and Rado implies that for

, any colouring of the edges of

upper K Subscript n K n $K_n$

with

n n $n$

sufficiently large gives a copy of

upper C Subscript 2 k C 2 k $C_{2k}$

which has one of three canonical colour patterns: monochromatic, rainbow or lexicographic. In this paper we show that if

p equals omega left parenthesis n Superscript negative 1 plus 1 divided by left parenthesis 2 k minus 1 right parenthesis Baseline log n right parenthesis p = ω ( n − 1 + 1 / ( 2 k − 1 ) log ⁡ n ) $p=\omega (n^{-1+1/(2k-1)}\log n)$

, then

bold upper G left parenthesis n comma p right parenthesis G ( n , p ) ${\mathbf G}(n,p)$

will asymptotically almost surely also have the property that any colouring of its edges induces canonical copies of

upper C Subscript 2 k C 2 k $C_{2k}$

. This determines the threshold for the canonical Ramsey property with respect to even cycles, up to a

log log $\log$

factor.