10 E. FRIEDGUT , V. RODL, A. RUCINSKI, AND P. TETALI
LEMMA
2.4. Let G £ Q \7Z be a graph with \V(G)\ 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.
Previous Page Next Page