Abstract

Rdl and Rucinski have extended Ramseys Theorem to random graphs, showing that there is aconstant C' such that with high probability, any two-colouring of the edges of G(n, p) with edgeprobability p= C'n?/(t+1) contains a monochromatic copy of Kt (the complete t-vertex graph). Weinvestigate how this statement extends to arbitrary colourings of G(n,p). Namely, when noassumptions are made on the edge colouring, one can only hope to find one of the four canonicacolourings of Kt, as in the well-known canonical version of Ramseys Theorem due to Erdös andRado. We show that indeed, any colouring of G(n,p) with p=Cn?/(t+1) contains a canonicallycoloured copy of Kt. As a consequence, the proof yields Kt+i-free graphs-G for which every edgecolouring contains a canonically coloured K. A crucial tool in our proof is the transference principledeveloped by Conlon and Gowers. Joint work with Mathias Schacht.

Speaker Intro

Nina KamÃev is an associate professor at the University of Zagreb. Her research interestsinclude extremal combinatorics, Ramsey theory, random graphs and processes, asymptoticenumeration, and arithmetic combinatorics. She obtained her Ph.D. from ETH Zurich in 2018 undelthe supervision of Benny Sudakov. From 2018 to 2023, she held research positions at MonashUniversity and at the University of Zagreb, where she was supported by the Widening Fellowshipfrom the EU Horizon 2020 programme. She was awarded the CMSA Prize by the CombinatoriaMathematics Society of Australasia in 2023.