Ramsey properties of randomly perturbed dense graphs

Abstract

We investigate Ramsey properties of a random graph model in which random edges are added to a given dense graph. Specifically, we determine lower and upper bounds on the function $p=p(n)$ that ensures that for any dense graph $G_n$ a.a.s. every 2-colouring of the edges of $G_n\cup G(n,p)$ admits a monochromatic copy of the complete graph $K_r$. These bounds are asymptotically sharp for the cases when $r\ge 5$ is odd and almost sharp when $r\ge 4$ is even. Our proofs utilise recent results on the threshold for asymmetric Ramsey properties in $G(n,p)$ and the method of dependent random choice.

13 pages

References in corpus (1)

• Adding random edges to create the square of a Hamilton cycle