2. OUTLINE OF THE PROOF
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"
• 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.