A Sharp Threshold for Random Graphs with a Monochromatic Triangle in Every Edge Coloring
Seiten
2005
|
illustrated Edition
American Mathematical Society (Verlag)
978-0-8218-3825-9 (ISBN)
American Mathematical Society (Verlag)
978-0-8218-3825-9 (ISBN)
- Titel z.Zt. nicht lieferbar
- Versandkostenfrei
- Auch auf Rechnung
- Artikel merken
Presents generalization of Szemeredi's Regularity Lemma to a certain hypergraph setting.
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 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 /cal{R} /right] /rightarrow 0$ and $Pr /left[G(n,(1+/varepsilon)/widehat c//sqrt{n}) /in /cal{R}/ /right] /rightarrow 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 setting.
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 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 /cal{R} /right] /rightarrow 0$ and $Pr /left[G(n,(1+/varepsilon)/widehat c//sqrt{n}) /in /cal{R}/ /right] /rightarrow 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 setting.
Introduction Outline of the proof Tepees and constellations Regularity The core section (Proof of Lemma 2.4) Random graphs Summaryt, further remarks, glossary Bibliography.
| Erscheint lt. Verlag | 1.2.2006 |
|---|---|
| Reihe/Serie | Memoirs of the American Mathematical Society |
| Zusatzinfo | illustrations |
| Verlagsort | Providence |
| Sprache | englisch |
| Gewicht | 165 g |
| Themenwelt | Mathematik / Informatik ► Mathematik ► Graphentheorie |
| ISBN-10 | 0-8218-3825-3 / 0821838253 |
| ISBN-13 | 978-0-8218-3825-9 / 9780821838259 |
| Zustand | Neuware |
| Informationen gemäß Produktsicherheitsverordnung (GPSR) | |
| Haben Sie eine Frage zum Produkt? |
