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

LEMMA

2.4. Let G £ Q \7Z be a graph with \V(G)\ — n n± for which the

assumption (3) of Theorem 2.1 holds. Then for every r 0 there exists a family

CORE of subgraphs of G such that

(a) For every triangle-free coloring \ °f E(G), there exists K G CORE which

is monochromatic under x-

(b) |CORE| exp(rn3/2),

(c) For every K G CORE we have \K\ \\E(G)\.

After thorough preparations in Sections 3 and 4, the family CORE will be

constructed in Section 5. Also there, all three conclusions of the above lemma will

be proven in the following manner:

(a) follows from Lemma 3.5 and Lemma 5.1,

(b) is Lemma 5.2, and

(c) follows from Lemma 3.5, Lemma 5.3 and Property (P3) of Q.

A specific value of r, with which we apply Lemma 2.4, is provided by another

application of Janson's inequality. We say that a subgraph F C G survives if

F U G(n, £p) has a triangle-free coloring in which F is monochromatic.

LEMMA

2.5. For every K € CORE, the probability that K survives is at most

exp {—2ron3//2}, where

a2ec6

T

° ~ 2 «

3

c

3

+

2£5C5)'

Proof: By Lemma 2.4(c) and the fact that G G T(A,a) there are at least

an3

triangles in Base(X). Let us number some

an3

of them by 1,2,...,

an3

and let Ii

be the indicator random variable for the event that the ith. triangle is contained in

G(n,&). Clearly, if K survives then £ \ U = 0. But, by [16], Theorem 2.18(h),

where the double sum is over all ordered pairs of distinct, edge-intersecting triangles

in Base(if). Note that

J2%E^

=

an3(£p)3 a£3c3n3/2

and that the double sum

contains at most n4 summands, each equalling at most (£p)5 (£C)5n_5//2. This

completes the proof. •

Let us now show how Lemmas 2.4 and 2.5 imply Theorem 2.1, and consequently

Theorem 1.1. We refer to the members of CORE by the name cores.

Proof of Theorem 2.1: Lemma 2.4(a) implies that if G U G(n,£p) has a proper

coloring x (which, of course, induces a triangle-free coloring of G) then there exists

a core which survives. But, using Lemma 2.4(b) with T = To, Lemma 2.5 and a

simple union bound, we deduce that with probability 1 — o(l) no core survives.

Indeed,

Pr[Any core survives]

exp{ron3/2}

•

exp{—2r0n3/2}

= o(l).

T T

# of cores survival probability

Hence Pr[G U G(n,£p) eTZ] = l - o(l) as required.

•