2. OUTLINE OF THE PROOF

G\ 2-colored G\

FIGURE

1. No triangle-free coloring of G\ U A can extend the given one

of a correlation estimate from [15] (see[16], Section 2.2), often called Janson's

inequality, at least one of these triangles will be included in G2 with very high

probability. If we were allowed to take 62 sufficiently large, then we could make

the reciprocal of the error probability larger than the exponential number of all

bi-colorings of Gi, proving G\ U G2 G 1Z with probability 1 — o(l).

Unfortunately, in our case 62 = £&i depends on a given a priori £ and can be

much smaller than b\. This major difficulty demonstrates a more general problem

of establishing a sharp threshold without knowing up front what the exact value of

the critical constant c should be.

Hence we must seek a refinement of the above approach, making use of the

assumption (3). And indeed, through a special regularization of G we will be able

to construct a family CORE of subgraphs of G such that for every triangle-free

coloring of G at least one of these subgraphs is monochromatic. Moreover, the size

of each subgraph K G CORE will be large enough to yield, via Lemma 2.3 and

Janson's inequality, at least one triangle in Base(If) H G(n, £p) with probability

very close to one, but at the same time the size of this family, |CORE|, multiplied

by the error probability will tend to 0. This is the content of the following two

lemmas which together imply Theorem 2.1. They are preceded by a setup, which

we will often be referring to in the paper.

Setup: For the rest of the paper, let us fix constants a,£ 0, a sequence

c/y/n p = p(n) C/y/n, where c = C2 and C = C2, and a graph M 0 1Z as

in Theorem 2.1 (it is no longer relevant that M is balanced). We will define a

graph property Q in Definition 6.1 so that, in particular, each G G Q has Property

T(A, a) with A = A(a, c, C, M) to be specified later (or see the Glossary now) and

a = a(A, c) determined by Lemma 2.3.

We do not attempt to compute explicitly the integer ni, promised in Theo-

rem 2.1 and appearing in the next lemma. In principle, it is the maximum of all

values of no encountered throughout the proof, most notably the no's in Theo-

rem 4.10 and Lemma 4.13, as well as of several implicit lower bounds on n hidden

in our calculations.