Canonical colourings in random graphs

Abstract

Rödl and Ruciński (1990) established Ramsey's theorem for random graphs. In particular, for fixed integers $r$, $\ell \ge 2$ they showed that ${\hat{p}}_{K_{\ell },r}(n)=n^{-\frac{2}{\ell +1}}$ is a threshold for the Ramsey property that every $r$-colouring of the edges of the binomial random graph $G(n,p)$ yields a monochromatic copy of $K_{\ell }$. We investigate how this result extends to arbitrary colourings of $G(n,p)$ with an unbounded number of colours. In this situation, Erdős and Rado showed that canonically coloured copies of $K_{\ell }$ can be ensured in the deterministic setting. We transfer the Erdős-Rado theorem to the random environment and show that both thresholds coincide for $\ell \ge 4$. As a consequence, the proof yields $K_{\ell +1}$-free graphs $G$ for which every edge colouring contains a canonically coloured $K_{\ell }$. The $0$-statement of the threshold is a direct consequence of the corresponding statement of the Rödl-Ruciński theorem and the main contribution is the $1$-statement. The proof of the $1$-statement employs the transference principle of Conlon and Gowers.

25 pages plus appendix, second version addresses minor changes arising from the referee reports