2003/01/19 by Ehud Friedgut, Vojtěch Rödl, Vojtech Rodl +7 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Limits and Structures in Graph Theory #math.CO #msc:05C15 #msc:05C55
paper · pdf · doi:10.48550/arxiv.math/0301200
101 pages, Final version - to appear in Memoirs of the A.M.S
arxiv created 2004/10/18 · arxiv updated 2009/11/30
Let \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 c= c(n) with 0<c< c<C such that for any \eps > 0, as n tends to infinity Pr[G(n,(1-\eps) c/√(n)) ∈ \R ] → 0 and Pr [ G(n,(1+\eps) c/√(n)) ∈ \R ] → 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.