A sharp threshold for random graphs with a monochromatic triangle in every edge coloring / Ehud Friedgut [and three others].

Format:

Book

Author/Creator:

Friedgut, Ehud, 1965- author.

Contributor:

Friedgut, Ehud, 1965-

Series:

Memoirs of the American Mathematical Society ; no. 845.

Memoirs of the American Mathematical Society, 0065-9266 ; number 845

Language:

English

Subjects (All):

Graph coloring.

Ramsey theory.

Random graphs.

Physical Description:

1 online resource (80 p.)

Edition:

1st ed.

Place of Publication:

Providence, Rhode Island : American Mathematical Society, [2006]

Language Note:

English

Summary:

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,$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 acertain hypergraph setting.

Contents:

""Contents""; ""1. Introduction ""; ""2. Outline of the Proof ""; ""3. Tepees and Constellations ""; ""4. Regularity ""; ""5. The Core Section (Proof of Lemma 2.4) ""; ""6. Random Graphs ""; ""7. Summary, Further Remarks, Glossary ""; ""Bibliography ""

Notes:

"Volume 179, number 845 (fourth of 5 numbers)."

Includes bibliographical references (pages 65-66).

Description based on print version record.

ISBN:

1-4704-0446-X