4 E. FRIEDGUT , V. RODL, A. RUCINSKI, AND P. TETALI

Otherwise we say that Q has a coarse threshold.

Thus, the property of being connected has a sharp threshold at p — log n/n.

Our main theorem in this paper, Theorem 1.1, states that the Ramsey property 1Z

has a sharp threshold.

In [8] the first author gives a necessary and sufficient condition for an increasing

property to have a sharp threshold. This condition will be the central tool used in

this paper. Roughly stated, it says that a property with a sharp threshold is not

statistically determined by a simple local reason, that is, by the presence or absence

of finitely many edges. For example, the property of having a triangle as a subgraph

is obviously local, and indeed has a coarse threshold (both the critical probability

and the length of the threshold interval equal 6(l/n)), whereas it seems obvious

that connectivity is a non-local property, even though it is statistically equivalent

to the absence of isolated vertices.

For the Ramsey property 7£, the condition in [8] asserts that in order to estab-

lish the sharpness of its threshold, one has to show that 1Z is not influenced by the

appearance of any fixed subgraph, which is likely to be contained in G(n,p), with

the range of p = p(n) limited by Theorem 1.2 to p = Q(l/y/n). Of course, 1Z is

extremely influenced by the appearance of KQ, which, however, is very unlikely to

be present in such a G(n,p).

In this paper we will use a version of the sharpness criterion from [8], which

follows readily from the original statement but is more suitable for applications.

Given a graph M and a disjoint set of n vertices, let M* be an ordered copy of M

placed uniformly at random on one of the n\/(n — |F(M)|)! possible locations.

THEOREM

1.3. Let Q be an increasing graph property, with a coarse threshold.

Then there exist real constants 0cC,(30, a rational p, and a sequence

p = p(n) satisfying cn~1/p p(n) Cn~1/p, such that (5 Pr[G(n,p) G Q] 1-/3

for all n. Furthermore, there exist a,£ 0 and a balanced graph M with density p

for which the following holds:

For every graph property Q such that G(n,p) G Q a.a.s. there are infinitely many

values of n for which there exists a graph G on n vertices for which the following

holds:

(i) G e g ,

(ii) G £ Q ,

(hi) Pr[(GUM*) G2] 2a,

(iv) Pr[(GuG(n^p))eQ] a .

What the theorem says, intuitively, is that in the case of a coarse threshold one

can find two graphs, G and M as follows: G is a fixed graph on n vertices that is

not a random graph but rather a pseudorandom graph, typical of G(n,p) (actually

a random choice of G G G(n,p) \ Q will work with probability close to 1); M is

a "magical" balanced graph such that it is often the case that adding a random

copy of M to G induces the property in question, whereas increasing the number

of edges in G randomly by a constant proportion £ does not induce the property.

The addition of a copy of M corresponds roughly to inducing a local property, in

contrast to increasing the number of edges which corresponds roughly to increasing

the global density of a random graph. Therefore the conclusion of the hypotheses

of the theorem is that the property Q is "statistically local".