
A Sharp Threshold for Random Graphs with a Monochromatic Triangle in Every Edge Coloring
American Mathematical Society (Publisher)
Will be published approx. on 30. December 2005
Book
Paperback/Softback
66 pages
978-0-8218-3825-9 (ISBN)
Description
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 Szemeredi's Regularity Lemma to a certain hypergraph setting.
More details
Series
Edition
illustrated Edition
Language
English
Place of publication
Providence
United States
Target group
College/higher education
Professional and scholarly
Illustrations
illustrations
Weight
165 gr
ISBN-13
978-0-8218-3825-9 (9780821838259)
Copyright in bibliographic data and cover images is held by Nielsen Book Services Limited or by the publishers or by their respective licensors: all rights reserved.
Schweitzer Classification
Content
Introduction Outline of the proof Tepees and constellations Regularity The core section (Proof of Lemma 2.4) Random graphs Summaryt, further remarks, glossary Bibliography.