A Sharp Threshold for Random Graphs with a Monochromatic Triangle in Every Edge Coloring

Let $cal{R}$ be the set of all finite graphs $G$ with the Ramsey property that every coloring of the edges of $G$ by two colors yields a monochromatic triangle. In this paper the authors establish a sharp threshold for random graphs with this property. Let $G(n, p)$ be the random graph on $n$ vertices with edge probability $p$. The authors prove that there exists a function $widehat c=widehat c(n)=Theta(1)$ such that for any $varepsilon > 0$, as $n$ tends to infinity, $Prleft G(n, (1-varepsilon)widehat c/sqrt{n}) in cal{R} ight] ightarrow 0$ and $Pr left G(n, (1]varepsilon)widehat c/sqrt{n}) in cal{R} ight] ightarrow 1.$. A crucial tool that is used in the proof and is of independent interest is a generalization of Szemeredi's Regularity Lemma to a certain hypergraph setti