A sharp threshold for random graphs with a monochromatic triangle in every edge coloring. Memoirs of the American Mathematical Society; 845.

Rodl, Vojtech; Rucinski, Andrzej

ISBN 10: 0821838253 / ISBN 13: 9780821838259

Published by Providence, American Math. Society, 2006

About this Item

Ex-library in GOOD condition with library-signature and stamp(s). Some traces of use. Ehem. Bibliotheksexemplar mit Signatur und Stempel. GUTER Zustand, ein paar Gebrauchsspuren. C-00281 9780821838259 Sprache: Englisch Gewicht in Gramm: 150.

Seller Inventory # 2482789

Bibliographic Details

• Title: A sharp threshold for random graphs with a monochromatic triangle in every edge coloring. Memoirs of the American Mathematical Society; 845.
• Publisher: Providence, American Math. Society
• Publication Date: 2006
• Language: English
• ISBN 10: 0821838253
• ISBN 13: 9780821838259
• Binding: Softcover
• Weight: 150 grams
• Seller catalogs:
  • SA MATHEMATIK

About this title

Synopsis

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.