2023/03/20 by Kamčev, Nina, Schacht, Mathias · 2 citations
#05C55 #05C80 #05D10 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2303.11206
Rödl and Ruciński (1990) established Ramsey's theorem for random graphs. In particular, for fixed integers r, ℓ≥ 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 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 for ℓ≥ 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.