**Memoirs of the American Mathematical Society**

2006;
66 pp;
Softcover

MSC: Primary 05;

Print ISBN: 978-0-8218-3825-9

Product Code: MEMO/179/845

List Price: $59.00

AMS Member Price: $35.40

MAA Member Price: $53.10

**Electronic ISBN: 978-1-4704-0446-8
Product Code: MEMO/179/845.E**

List Price: $59.00

AMS Member Price: $35.40

MAA Member Price: $53.10

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

Share this page
*Ehud Friedgut; Vojtech Rödl; Andrzej Ruciński; Prasad Tetali*

Let \(\mathcal{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 we 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\). We prove that there exists a function \(\widehat c=\widehat c(n)=\Theta(1)\) such that for any \(\varepsilon > 0\), as \(n\) tends to infinity, \(Pr\left[G(n,(1-\varepsilon)\widehat c/\sqrt{n}) \in \mathcal{R} \right] \rightarrow 0\) and \(Pr \left[ G(n,(1+\varepsilon)\widehat c/\sqrt{n}) \in \mathcal{R}\ \right] \rightarrow 1\). A crucial tool that is used in the proof and is of independent interest is a generalization of Szemerédi's Regularity Lemma to a certain hypergraph setting.