Abstract
Let 1Z 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 Z = ?(n) = 0(1) such that for any e 0, as n tends to
infinity,
Pr [G(n, (1 - e)c/^/7i) G K] - 0
and
Pr [G(n, (1 + e)c/y/n) G U ] - 1.
A crucial tool that is used in the proof and is of independent interest is a general-
ization of Szemeredi's Regularity Lemma to a certain hypergraph setting.
Received by the editor January 29, 2003, and in revised form August 17, 2004.
2000 Mathematics Subject Classification. Primary 05C15; Secondary 05C55, 05C80.
Key words and phrases. Ramsey Theory, Random Graphs, Threshold Phenomena, Szemeredi 's
Regularity Lemma.
Research supported by grants of the ISF, BSF, NSF, and KBN. For details see section 7.1.
Previous Page Next Page