1. Introduction
1.1. Overview. This paper brings together several important themes of com-
binatorics: Ramsey properties, threshold phenomena of random graphs, and Sze-
meredi-type regularity.
Ramsey properties guarantee, for an arbitrary partition of a given structure,
that a highly organized substructure can be found in at least one part of the parti-
tion. During the last decade of the last century there has been extensive study of
Ramsey properties of random structures, see e.g. [11, 27, 29, 30, 31, 32, 13, 33].
These papers were all concerned with establishing a threshold function for various
Ramsey-type properties, either of random graphs, random hypergraphs or random
sets of integers. For a binomial random graph G(n,p(n)), for instance, they provide
a critical edge probability p = p{ri) such that the limiting probability that every
coloring of a random graph G(n,p) contains certain monochromatic structures de-
pends on the asymptotic ratio between p and p.
In all the above papers there is a multiplicative gap left between the upper and
lower bound on the threshold edge probability p (see Theorem 1.2 below). It is
therefore not surprising that the natural question of whether the gap can be closed
has been around for some time. In other words, does there exist a constant c such
that the asymptotic probability that G(n, dp) has a Ramsey property is either 0 or
1, depending only on whether c c or c c? This question is usually phrased in
the specialized jargon as "does there exist a sharp threshold!"
Sharp thresholds have been established for many random graph properties, like
connectivity, hamiltonicity and perfect matchings. However, such precise results
for Ramsey properties seemed out of hand until 1999, when a general technique
for settling these questions was introduced in [8]. Loosely speaking, the main
theorem in [8] showed that the question of sharpness of threshold for a random
graph property is determined by whether the property is related to local or rather
global graph phenomena.
Two papers exploiting the technique from [8] for coloring questions are [1]
and [10]. The latter paper (as well as the earlier [31]) states as the next natural
candidate for attack, the problem of sharpness of the threshold for property 1Z
consisting of all graphs G such that in every blue-red coloring of the edges of G
there exists a monochromatic triangle. However, this problem turned out to be
more difficult than those in [1] and [10] and required some new combinatorial
In this paper we add the missing tool that enables us to crack this nut. It is
a regularity lemma for a certain class of hypergraphs, whose edges consist of small
subgraphs of a fixed underlying sparse graph (see Lemma 4.13). Our lemma is a
generalization of the celebrated Szemeredi Regularity Lemma for graphs [35], and
follows in the footsteps of the regularity lemma for sparse graphs presented in [20]
(see also [22] and [16], Section 8.3) and of the hypergraph regularity lemma of
Frankl and Rodl [12].
The proof of our regularity lemma, Lemma 4.13, provides for a considerable
portion of the bulk of the proof of the following sharp threshold theorem, which is
the ultimate result of our paper.
Previous Page Next Page