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

Note that if the assumption G ^ 1Z (Assumption (ii) in Theorem 1.3) were

false then (4) would be trivial. A finer point is that if M G 1Z then (3) yields no

information on G, and hence is useless. Fortunately the following lemma rules out

this possibility. This is the typical "easy step" mentioned in the introduction.

LEMMA

2.2. If M is balanced and p(M) = 2 then M 0 1Z.

Proof: It is a well known fact from the theory of random graphs (see [16], page

66) that for any balanced graph H with p(H) — p and p = Q(n~1/p) there exists a

constant j3 0 such that the probability that H appears in G(n,p) is at least (3.

Hence, for any b 0, the probability that M appears as a subgraph of G(n, b/y/n)

is bounded away from zero. If M G 1Z then, by the monotonicity of 1Z, this

would mean that Pr[G(n, b/y/n) G 1Z] is also bounded away from zero. But by

Theorem 1.2, for all b c2, Pr[G(n, b/y/n) G K] - • 0. Therefore M (£K.

Alternatively, and without the use of random graphs, Lemma 2.2 follows from

a result in [25] which shows that any Ramsey graph (for K3) must have a subgraph

H for which p(H) 5/2. •

The rest of the paper is devoted to proving that (3) implies (4). An approach

to statements like (4), which has become standard by now, is via the so called

two round exposure. This technique originated in the seventies, in work of Posa,

Ajtai, Komlos, Szemeredi, Fernandez de la Vega, Fenner and Frieze, devoted to the

existence of Hamilton paths and cycles in random graphs (see [3], Chapter VIII,

for references). In the context of Ramsey properties, it was explored already in [29]

and [30] (see also [15], Sections 1.1 and 8.4). For a graph G = (V, E) and a set of

edges F C E, let Base(F) be the set of edges in the complete graph on V that form

a triangle with two edges of F , formally:

Base(F) = {uv : uw, wv G F for some w G V}.

We often identify a subset of edges of a graph with the spanning subgraph consisting

of them. So, in the above, both F and Base(F) can be viewed as graphs on the

same vertex set V.

Suppose we want to show that G\ U G2 G 1Z with high probability, where

G{ = G(n, bi/y/n), i = 1, 2, and the two random graphs are independent. (This is,

in fact, our case with 62 = £&i? except for two minor points: that G\ is not random

but pseudorandom, and that b\ may depend on n.)

First generate the edges of Gi, and let them be colored by an adversary. Sup-

pose that at least half of them are blue and call the set of blue edges Blue. Clearly,

if Ba,se(Blue) contains a triangle A, no proper coloring of G\ U A can extend the

adversarial coloring. Therefore, it will suffice to show that Base(i3/i£e)nG2 contains

a triangle. (See Figure 1.)

To this end we utilize the following lemma, proved in Section 6. Given two real

numbers 0 A 1 and 0 a 1/6, we say that a graph G has property T(A, a),

if for any subgraph F of G with at least A|£'(G)| edges, the graph Base(F) contains

at least a|F(G)| 3 triangles.

LEMMA

2.3. For all A 0 and c 0, there exists a 0, such that if p c/y/n

then, with probability 1 — o{\), the random graph G{n,p) has property T(A,a).

Applying the above lemma with F = Blue, A = 1/2 and c = b\ would yield

6(n 3 ) triangles in Base(jBZwe). In the second round, by a standard application