6 E. FRIEDGUT , V. RODL, A. RUCINSKI, AND P. TETALI
The idea of regularity has also been extended to uniform hypergraphs. The
version that is most relevant to us is the one in Frankl and Rodl , which makes
it possible to decompose triple systems into quasi-random structures made up of
triples together with an 'underlying' quasi-random tripartite graph. In that setting,
the density is measured by the ratio of triples to the triangles in the underlying
graph (see Section 4.2.1). Moreover, the concept of quasi-randomness here is strong
enough to allow one to prove that these quasi-random pieces contain the same
number of finite substructures as they would had they been truly random pieces
(see  and Nagle and Rodl ).
In this paper, we shall introduce yet another concept of regularity, which ex-
pands and melts together the notions of sparse graph regularity and hypergraph
regularity. In the usual context of graph regularity, and in some more delicate
versions of it there is an invisible underlying graph behind the graph we look at,
and the regularity expresses the distribution of specified edges with respect to the
edges of the underlying graph. Similarly, a 3-uniform hypergraph can be viewed
as a distinguished collection of triangles among all triangles of an underlying 3-
partite graph. Here, we shall be interested in investigating the structure of sparse
graphs with respect to some other fixed family of small subgraphs. Viewing these
subgraphs as edges of a hypergraph, the lemma we prove (Lemma 4.13) may be
interpreted as a sparse hypergraphs version of the regularity lemma . Our approach
is partly based on methods from [20, 23] and , but it faces a further difficulty:
the assumption of 'no dense patches' in the standard case (see [20, 23]) was an
easy consequence of properties of random graphs and therefore did not play any
significant role; the proof of the analogous fact in the setting of this paper, however,
requires a fairly complex argument (see Section 4.4).
1.5. Outline of the Paper.
• In Section 2 we present the skeleton of the proof of the main theorem.
It is actually a formal proof which is made extremely short and compact
by relying on lemmas which will be proven in the rest of the paper. An
overview of the forthcoming proofs and an (oversimplified) illustration will
also be given there.
• In Section 3, assuming the hypothesis of Theorem 1.3, we construct a
family S of special subgraphs of G (called special constellations) and show
how every triangle-free coloring of G defines a set of edges of G that
intersects all special constellations (that is, defines a hitting set for the
• In Section 4 we prove a regularity theorem in the spirit of Szemeredi's
Regularity Lemma that provides a partition of both the vertices and the
edges of G such that the special constellations are uniformly distributed
with respect to this partition.
• In Section 5, based on the regular partition found in the previous section,
we define a core which is a central notion of this proof, and show some
crucial properties of cores.
• In Section 6 we show various properties of random graphs that are needed
throughout the paper. It is there where the family Q is defined, and an
important lemma, Lemma 2.3, is proved.
• We conclude with open questions and possible extensions.