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
Previous Page Next Page