Sharp Threshold for Random Graphs with a Monochromatic Triangle in Every Edge Coloring (eBook)

Ehud Friedgut (Autor)

eBook Download: PDF

66 Seiten
American Mathematical Society (Verlag)
978-1-4704-0446-8 (ISBN)

Infos

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

Produkt-Details

• Themenwelt: Mathematik / Informatik ► Mathematik ► Graphentheorie
• ISBN-10: 1-4704-0446-X / 147040446X
• ISBN-13: 978-1-4704-0446-8 / 9781470404468