Canonical colourings in random graphs

Rödl and Ruciński (1990) established Ramsey’s theorem for random graphs. In particular, for fixed integers $r$, $\mathrm{\ell }\ge 2$ they showed that ${\widehat{p}}_{K_{\mathrm{\ell }},r}(n)=n^{-\frac{2}{\mathrm{\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_{\mathrm{\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_{\mathrm{\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 $\mathrm{\ell }\ge 4$. As a consequence, the proof yields $K_{\mathrm{\ell }+1}$-free graphs $G$ for which every edge colouring contains a canonically coloured $K_{\mathrm{\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.