An error was encountered while trying to add the item to the cart. Please try again.
Copy To Clipboard
Successfully Copied!
A Sharp Threshold for Random Graphs with a Monochromatic Triangle in Every Edge Coloring

Ehud Friedgut Hebrew University, Jersulem, Israel
Vojtech Rödl Adam Mickiewicz University, Poznán, Poland
Andrzej Ruciński Georgia Institute of Technology, Atlanta, GA
Available Formats:
Electronic ISBN: 978-1-4704-0446-8
Product Code: MEMO/179/845.E
List Price: $59.00 MAA Member Price:$53.10
AMS Member Price: $35.40 Click above image for expanded view A Sharp Threshold for Random Graphs with a Monochromatic Triangle in Every Edge Coloring Ehud Friedgut Hebrew University, Jersulem, Israel Vojtech Rödl Adam Mickiewicz University, Poznán, Poland Andrzej Ruciński Georgia Institute of Technology, Atlanta, GA Available Formats:  Electronic ISBN: 978-1-4704-0446-8 Product Code: MEMO/179/845.E  List Price:$59.00 MAA Member Price: $53.10 AMS Member Price:$35.40
• Book Details

Memoirs of the American Mathematical Society
Volume: 1792006; 66 pp
MSC: Primary 05;

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.

• Chapters
• 1. Introduction
• 2. Outline of the proof
• 3. Tepees and constellations
• 4. Regularity
• 5. The core section (proof of Lemma 2.4)
• 6. Random graphs
• 7. Summary, further remarks, glossary
• Requests

Review Copy – for reviewers who would like to review an AMS book
Permission – for use of book, eBook, or Journal content
Accessibility – to request an alternate format of an AMS title
Volume: 1792006; 66 pp
MSC: Primary 05;

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.

• Chapters
• 1. Introduction
• 2. Outline of the proof
• 3. Tepees and constellations
• 4. Regularity
• 5. The core section (proof of Lemma 2.4)
• 6. Random graphs
• 7. Summary, further remarks, glossary
Review Copy – for reviewers who would like to review an AMS book
Permission – for use of book, eBook, or Journal content
Accessibility – to request an alternate format of an AMS title
Please select which format for which you are requesting permissions.