A Sharp Threshold for Random Graphs with a Monochromatic Triangle in Every Edge Coloring
| Author/creator | Friedgut, Ehud, 1965- Author |
| Other author | R©œdl, Vojtech Author |
| Other author | Rucinski, Andrzej Author |
| Other author | Tetali, Prasad Author |
| Format | Electronic |
| Publication Info | Providence : American Mathematical Society |
| Description | 66 p. ill 00.300 x 00.500 cm. |
| Supplemental Content | Full text available from Ebook Central - Academic Complete |
| Supplemental Content | Full text available from Memoirs of the American Mathematical Society - Backfile |
| Subjects |
| Series | Memoirs of the American Mathematical Society Ser. 179 |
| Summary | Annotation 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 Szemer©♭di's Regularity Lemma to acertain hypergraph setting. |
| Access restriction | Available only to authorized users. |
| Technical details | Mode of access: World Wide Web |
| Genre/form | Electronic books. |
| LCCN | 2005053660 |
| ISBN | 9780821838259 |
| ISBN | 0821838253 (Trade Paper) Active Record |
| Standard identifier# | 9780821838259 |
| Stock number | MEMO/179/845 00001436 |
Availability
| Library | Location | Call Number | Status | Item Actions |
|---|---|---|---|---|
| Electronic Resources | ✔ Available |