Mathias Schacht, Canonical colourings in random graphs

Rödl and Ruciński established Ramsey’s theorem for random graphs. In particular, for fixed integers $r$, $\ell \ge 2$ they showed that $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 for $\ell \ge 4$ both thresholds coincide. As a consequence the proof yields $K_{\ell +1}$-free graphs $G$ for which every edge colouring yields a canonically coloured $K_{\ell }$.

This is joint work with Nina Kamčev.