2. OUTLINE OF THE PROOF

11

2.2. Overview of the Proof Strategy. Clearly, at such an early point in

the paper, the main idea of the proof may yet be obscure. Specifically, we have

given no hint as to the connection between the existence of a magical graph M

having the property described in assumption (3) of Theorem 2.1 and the existence

of a family CORE satisfying the three conclusions of Lemma 2.4. In order to shed

some light on this connection (albeit it will still be a dim light), we give here a

short explanation of the logic and motivation behind the construction of CORE.

The next three sections of the paper are devoted to the constructions that underlie

the following scheme:

• The existence of M such that

Pr[GUM* ell] 2a

implies that the set of triangle-free colorings of G is very restricted; there

are many sets of vertices in G such that planting a copy of M on them

kills all triangle-free colorings, i.e. no triangle-free coloring of G can be

extended t o G u M when M is placed on one of the aforementioned "bad"

sets.

• We will associate every such "bad" set with a set of edges in G, a union

of stars which we will call a special constellation. We will fix a coloring

of these special constellations in such a way that every proper coloring of

G must agree with every such colored constellation on at least one edge

(see Lemma 3.2).

• The above can be translated to the language of hypergraphs: we will

construct a hypergraph whose hyperedges are the edge sets of the special

constellations, and it will turn out that every triangle-free coloring gives

rise to a hitting set of the hyperedges of this hypergraph (see Lemma 3.5).

• We will show that every such hitting set (and hence every triangle-free

coloring) may be associated with a large monochromatic set called a core.

CORE is the family of cores (see Lemma 2.4 above).

• The key to associating every hitting set with a core is in showing that our

hypergraph has an inherent regular structure that may be revealed by a

Szemeredi type partition (see Lemma 4.13).

2.2.1. An Illustration. To get a better feeling of how regularity helps in creat-

ing the family CORE, let us consider a simpler analogue that takes place in the

well understood setting of graphs, in which special constellations will be replaced

simply by edges. Hopefully this will give some clue as to what we are doing in the

forthcoming sections. We refer the reader to Section 4 for the notion of an ^-regular

graph and the statement of the Szemeredi Regularity Lemma.

Let H = H(n) be a sequence of graphs on n vertices. A cover set in a graph is

a set of vertices that intersects every edge. In other words, it is a hitting set for the

family of all edges of the graph. In general, the number of cover sets in an n-vertex

graph may be exponential in n, and our goal is to "capture" all cover sets of H by

a smaller family of large subsets of vertices which we will call cores. (Elsewhere in

the paper the term core is used in our larger setting, cf. Lemma 2.4.) We want the

following properties to hold for cores:

• Every cover set contains a core,

• The number of cores is 2°^,

• Every core is of size linear in n.