The threshold for the asymmetric vertex-Ramsey property in randomly perturbed graphs

Abstract

For $r\ge 2$ and graphs $H_1,\dots ,H_r,G$, we say that $G$ is $(H_1,\dots ,H_r)$ vertex-Ramsey, or $(H_1,\dots ,H_r{)}_v$-Ramsey, if whenever we colour the vertices of $G$ with colours from the set $[r]=\{1,2,\dots ,r\}$ there exists $j\in [r]$ such that some copy of $H_j$ in $G$ is monochromatic in colour $j$. Given any fixed collection of graphs $H_1,\dots ,H_r$, Luczak, Ruciński and Voigt and Kreuter determined in the 1990s the threshold edge probability $p$ at which the binomial random graph $G(n,p)$ becomes $(H_1,\dots ,H_r{)}_v$-Ramsey. More recently, Das, Morris and Treglown investigated the vertex-Ramsey property in the randomly perturbed setting. When $r=2$ they determined the number of random edges one must add to a dense graph to ensure that with probability $1-o(1)$ the resulting graph is $(H_1,H_2{)}_v$-Ramsey whenever one of $H_1$ or $H_2$ is a clique. They posed the problem of extending their results to all pairs of graphs $(H_1,H_2)$. In this paper we resolve a more general form of their problem and determine for any $r\ge 2$ and $r$-tuple of graphs $(H_1,\dots ,H_r)$ the number of random edges one must add to a dense graph to ensure that with probability $1-o(1)$ the resulting graph is $(H_1,\dots ,H_r{)}_v$-Ramsey.