MATH Seminar
| Title: Canonical colourings in random graphs |
|---|
| Seminar: Combinatorics |
| Speaker: Mathias Schact of University of Hamburg |
| Contact: Liana Yepremyan, liana.yepremyan@emory.edu |
| Date: 2024-02-16 at 4:00PM |
| Venue: MSC W201 |
| Download Flyer |
| Abstract: 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