Canonical colourings in random graphs

• Published in: Procedia computer science 2023, Vol.223, p.5-12
• Main Authors: Kamčev, Nina, Schacht, Mathias
• Format: Article
• Language: English
• Subjects: canonical colourings; Ramsey's theorem; Random graphs; thresholds
• ISSN: 1877-0509; 1877-0509
• DOI: 10.1016/j.procs.2023.08.207

Rödl and Ruciński [Threshold functions for Ramsey properties, J. Amer. Math. Soc. 8 (1995)] established Ramsey's theorem for random graphs. In particular, for fixed integers r and ℓ ≥ 2 they showed that ˆpkℓ,r(n) = n-2/ℓ+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ℓ. We investigate how this result extends to arbitrary colourings of G(n,p) with an unbounded number of colours. In this situation, Erdős and Rado [A combinatorial theorem, J. London Math. Soc. 25 (1950)] showed that canonically coloured copies of Kℓ can be ensured in the deterministic setting. We transfer the Erdős-Rado theorem to the random environment and show that both thresholds coincide when ℓ ≥ 4. As a consequence, the proof yields Kℓ+1-free graphs G for which every edge colouring contains a canonically coloured Kℓ. The 0-statement of the threshold is a direct consequence of the corresponding statement of the Rödl-Ruciński theorem and the main contribution is the 1-statement. The proof of the 1-statement employs the transference principle of Conlon and Gowers [Combinatorial theorems in sparse random sets, Ann. of Math. (2) 184 (2016)].