Canonical colourings in random graphs
Organizer
Benjamin Sudakov
Speaker
Nina Kamčev
Time
Tuesday, May 14, 2024 5:05 PM - 6:15 PM
Venue
Online
Online
Zoom 787 662 9899
(BIMSA)
Abstract
Rödl and Ruciński have extended Ramsey’s Theorem to random graphs, showing that there is a constant $C$ such that with high probability, any two-colouring of the edges of $G(n, p)$ with edge probability $p = Cn^{−2/(t+1)}$ contains a monochromatic copy of $K_t$ (the complete $t$-vertex graph). We investigate how this statement extends to arbitrary colourings of $G(n, p)$. Namely, when no assumptions are made on the edge colouring, one can only hope to find one of the four canonical colourings of $K_t$, as in the well-known canonical version of Ramsey’s Theorem due to Erdős and Rado.
We show that indeed, any colouring of $G(n,p)$ with $p = Cn^{−2/(t+1)}$ contains a canonically coloured copy of $K_t$. As a consequence, the proof yields $K_{t+1}$-free graphs~$G$ for which every edge colouring contains a canonically coloured $K_t$. A crucial tool in our proof is the transference principle developed by Conlon and Gowers.
Joint work with Mathias Schacht.