| eBook 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 |
| eBook 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 DetailsMemoirs of the American Mathematical SocietyVolume: 179; 2006; 66 ppMSC: 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.
-
Table of Contents
-
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
-
-
RequestsReview Copy – for publishers of book reviewsPermission – for use of book, eBook, or Journal contentAccessibility – to request an alternate format of an AMS title
- Book Details
- Table of Contents
- Requests
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
