The threshold for the constrained Ramsey property

Abstract

Given graphs $G$, $H_1$, and $H_2$, let $G\stackrel{\text{mr}}{\to }(H_1,H_2)$ denote the property that in every edge colouring of $G$ there is a monochromatic copy of $H_1$ or a rainbow copy of $H_2$. The constrained Ramsey number, defined as the minimum $n$ such that $K_n\stackrel{\text{mr}}{\to }(H_1,H_2)$, exists if and only if $H_1$ is a star or $H_2$ is a forest. We determine the threshold for the property $G(n,p)\stackrel{\text{mr}}{\to }(H_1,H_2)$ when $H_2$ is a forest, explicitly when the threshold is $\Omega (n^{-1})$ and implicitly otherwise.

15 pages