MATH Seminar

Title: Canonical colourings in random graphs
Seminar: Combinatorics
Speaker: Mathias Schact of University of Hamburg
Contact: Liana Yepremyan,
Date: 2024-02-16 at 4:00PM
Venue: MSC W201
Download Flyer
Rodl and Rucinski established Ramsey's theorem for random graphs. In particular, for fixed integers $r$, $\ell\geq 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\H{o}s and Rado showed that \textit{canonically coloured} copies of~$K_\ell$ can be ensured in the deterministic setting. We transfer the Erd\H os--Rado theorem to the random environment and show that for $\ell\geq 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 Kamev.

See All Seminars