Speaker
Nina Kamčev, University of Zagreb
Abstract
Canonical Ramsey theorem in random graphs
R\”odl and Ruci\’nski have extended Ramsey’s Theorem to random graphs, showing that there is a large constant $C$ such that with high probability, any two-colouring of the edges of the random graph $G_{n,p}$ with $p = Cn^{-\frac{2}{\ell+1}}$ contains a monochromatic copy of $K_\ell$. We investigate how this result extends to arbitrary colourings of $G_{n,p}$. Namely, when no assumptions are made on the edge colouring of $G_{n,p}$, one can only hope to find one of the four \textit{canonical colourings} of $K_\ell$, as in the well-known canonical version of Ramsey’s Theorem due to Erd\H{o}s and Rado.
We show that indeed, with high probability, any colouring of $G_{n,p}$ with $p = Cn^{-\frac{2}{\ell+1}}$ contains a canonically coloured copy of $K_\ell$. As a consequence, the proof yields $K_{\ell+1}$-free graphs~$G$ for which every edge colouring contains a canonically coloured $K_\ell$. A crucial tool in our proof is the transference principle developed by Conlon and Gowers.
Joint work with Mathias Schacht.