A Sharp Threshold for Random Graphs With a Monochromatic Triangle in Every Edge Coloring (Memoirs of the American Mathematical Society) [Paperback]

Vojtech Rödl, Andrzej Rucinski, and Prasad Tetali Ehud Friedgut (Author)

Book Description

Publication Date: December 1, 2005 | ISBN-10: 0821838253 | ISBN-13: 978-0821838259

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 Szemerédi's Regularity Lemma to a certain hypergraph setting.

Product Details

• Paperback: 66 pages
• Publisher: American Mathematical Society (December 1, 2005)
• Language: English
• ISBN-10: 0821838253
• ISBN-13: 978-0821838259
• Product Dimensions: 9.8 x 6.5 x 0.2 inches
• Shipping Weight: 6.4 ounces (View shipping rates and policies)
• Amazon Best Sellers Rank: #9,975,418 in Books (See Top 100 in Books)