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

approach.

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.