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