We say a graph G is Ramsey for a pair of graphs (H₁, H₂) if any red-/blue-colouring of E(G) contains either a red H₁ or a blue H₂. Much research has been devoted to determining the thresholds at which the Erdős-Rényi random graph G(n,p) becomes Ramsey for (H₁, H₂). In this talk, we instead consider the perturbed random graph model, where one sprinkles some random edges on top of a deterministic dense graph, and ask how much less randomness is needed to ensure the resulting graph is Ramsey.

This line of research was initiated by Krivelevich, Sudakov and Tetali in 2006, who determined the thresholds for the pairs (K₃, K_t) with t ≥ 3. Here we extend their work, considering pairs of larger cliques. We also present results for cycles, and cycles versus cliques.

This is joint work with Andrew Treglown.