Beijing Institute of Mathematical Sciences and Applications

Benjamin Sudakov

Nina Kamčev

Tuesday, May 14, 2024 5:05 PM - 6:15 PM

Online

Zoom 787 662 9899 (BIMSA)

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.