The hypergraph regularity method and its applications

Main Result: The Removal Lemma

For a set V and an integer k ≥ 1, let be the set of all k-element subsets of V. A subset is a k-uniform hypergraph or k-graph for short, on the vertex set V.

The following result was conjectured by Erdős, Frankl, and Rödl (13) in the case where is a clique.

Theorem 5 (Removal Lemma). For all fixed integers l ≥ k ≥ 2 and every μ > 0 there exist ζ = ζ(l, k, μ) > 0 and n ₀ = n ₀(l, k, μ) so that the following holds. Suppose is a k-graph on l vertices and is a k-graph on n ≥ n ₀ vertices. If contains at most ζn ^l copies of , then one can delete μn^k edges of to make it -free.

Ruzsa and Szemerédi (14) proved Theorem 5 for k = 2 and being the triangle , the graph consisting of three edges on three vertices. Frankl and Rödl (15) proved Theorem 5 for k = 3 and , the 3-graph consisting of four triples on four vertices. These proofs follow what we call the regularity method for graphs and 3-graphs, respectively. Extending concepts developed in ref. 15, the regularity method for k-graphs was established in refs. 16 and 17. The proof of Theorem 5 for general k follows lines similar to those in refs. 14 and 15 [see ref. 17 for the case and ref. 18 for general ]. For illustrative purposes, we later sketch the derivation of Ruzsa and Szemerédi's result by using the regularity method for graphs.

We mention that Gowers (W. T. Gowers, personal communication; see also ref. 19) has also independently developed similar regularity techniques for proving Theorem 5. Very recently, Tao (T. Tao, personal communication) announced another proof of Theorem 5.

Applications

Before discussing the components of the regularity method for k-graphs, we turn to some applications of the removal lemma. As mentioned earlier, the removal lemma implies Theorems 1–4. This was shown for Theorem 1 by Frankl and Rödl in ref. 15. Subsequently, Solymosi (20) established a similar relation for Theorem 2. Elaborating on an idea from ref. 15, Tengan, Tokushige, V.R., and M.S. (21) derived the following common generalization of Theorems 3 and 4.

Theorem 6. Let A be a finite ring with q elements. For every δ > 0, there exists M ₀ = M ₀(q, δ) such that, for M ≥ M ₀, any subset Z ⊂ A^M with |Z| > δ|A^M| = δq^M contains a coset of an isomorphic copy of A (as a left A-module). In other words, there exist r, u ∈ A^M such that r + ϕ(A) ⊂ Z, where ϕ: A ↪ A^M, ϕ(α) = αu for α ∈ A, is an injection.

Theorem 5 also implies the affirmative answer to a geometric problem of Székely (ref. 22, p. 226): For a point c = (c ₁,..., c_k) in the k-fold cross-product of [n] with itself, we define the jack J(c) with center c as the set of points that differ from c in at most one coordinate. For 1 ≤ i ≤ k and fixed c ₁,..., c_{i -1}, c_{i +1},..., c_k ∈ [n], we also define a line as a set of n points of the form Let LS(n, k) be the maximum cardinality of a system J of jacks for which

1. no two distinct jacks share a common line; and

2. for all distinct jacks J ₁,..., J_k ∈ J.

The following result (18) gives a positive answer to Székely's problem.

Theorem 7. LS(n, k) = o(n^{k -1}).

As one would expect from the literature for graphs (see, e.g., ref. 23), the hypergraph regularity method also may be used to obtain further results in the areas of extremal and asymptotic hypergraph problems. Here we mention one such result.

Let ℱ be a finite family of k-graphs and let be the set of all labeled k-graphs not containing any as a subhypergraph. Moreover, let be those hypergraphs of with vertex set [n] and set Note that all subhypergraphs of any fixed also belong to , and in particular, this holds for achieving . The inequality thus follows. The next theorem (B.N., V.R., and M.S., unpublished data) asserts this bound is essentially best possible whenever ℱ satisfies .

Theorem 8. For any finite family ℱ of k-graphs,

Theorem 8 complements a collection of analogous theorems already proven for graphs (i.e., k = 2), and generalizes results from refs. 13, 24, and 25.

We now discuss the regularity method for graphs and hypergraphs.

Szemerédi's Regularity Lemma

In the course of proving Theorem 1, Szemerédi established a lemma that decomposes the edge set of any graph into relatively few “blocks,” almost all of which are random-like (10). In what follows, we give a precise account of Szemerédi's lemma.

A pair (A, B) of two disjoint vertex subsets A, B ⊂ V of a graph G = (V, E) is said to be ε-regular if for all A′ ⊂ A, B′ ⊂ B, where |A′| > ε|A|, |B′| > ε|B|, we have |d(A, B) - d(A′, B′)| < ε where d(A′, B′) = |E(A′, B′)|/(|A′∥B′|) and E(A′, B′) denotes the set of edges of G with an endpoint in each of A′ and B′. We denote by G[A, B] the bipartite subgraph of G induced on A and B, and we say that G[A, B]is ε-regular if (A, B) is ε-regular. Szemerédi's lemma may then be stated as follows.

Theorem 9 (Szemerédi's Regularity Lemma). Let ε > 0 be given and let t ₀ be a positive integer. There exists a positive integer T ₀ = T ₀(ε, t ₀) such that any graph G = (V, E) admits a partition V = V ₁ υ · · · υ V_t, t ₀ ≤ t ≤ T ₀, satisfying

1. |V ₁| ≤ · · · ≤ |V_t| ≤ |V ₁| + 1, and

2. all but at most pairs (V_i, V_j), 1 ≤ i < j ≤ t, are ε-regular.

Szemerédi's regularity lemma is a powerful tool in extremal graph theory. One of its most important consequences is that, in appropriate circumstances, it can be used to show that a given graph contains a fixed subgraph. This observation follows from the following well-known and easily proved fact, which may be called the “counting lemma” for graphs.

Fact 10 (Counting Lemma). For all positive integers l and d > 0 and γ > 0 there exists ε = ε(l, d, γ) > 0 so that the following holds. Let G = υ_1≤i<j≤l G^ij be an l-partite graph with l-partition V₁ υ · · · υ V_l, where G^ij = G[V_i, V_j], 1 ≤ i < j ≤ l, and |V ₁| = · · · = |V_l| = n. Suppose further that each graph G^ij, 1 ≤ i < j ≤ l, is ε-regular with density d. Then the number_l of copies of the l-clique K_l in G is within the interval .

We refer to the combined application of Theorem 9 and Fact 10 as the regularity method for graphs. This method yields Theorem 5 in the case of graphs (k = 2), the proof of which can be traced to Ruzsa and Szemerédi (14). We now sketch this proof in the special case in which is the triangle.

We first address the promised constants. To that end, let μ > 0 be given. To define ζ = ζ(3, 2, μ) > 0, we first let γ = 1/2, d ₀ = μ/3, and t ₀ = ⌈3/μ⌉ and take ε = ε(3, d ₀, γ) > 0 to be the constant guaranteed by Fact 10. Without loss of generality, we may assume that ε < μ/3. For t ₀ = ⌈3/μ⌉ and ε defined above, let T ₀ = T ₀(ε, t ₀) be the constant guaranteed by Theorem 9. We define . We take n ₀ sufficiently large whenever needed.

Suppose is a graph on n ≥ n ₀ vertices and suppose H contains at most ζn ³ copies of the triangle . We exhibit a triangle-free subgraph H′ of H with only μn ² fewer edges and do so by appealing to the regularity lemma, Theorem 9.

Indeed, with input parameters ε > 0 and t ₀ previously defined, apply Theorem 9 to the graph H to obtain a partition V(H) = V ₁ υ · · · υ V_t, t ₀ ≤ t ≤ T ₀, satisfying the properties in the conclusion of that theorem. Note that the constant T ₀, guaranteed by Theorem 9, is the same as we considered earlier when defining ζ. To obtain the promised triangle-free subgraph H′, delete from H any edge {v_i, v_j} ∈ E(H), v_i ∈ V_i, v_j ∈ V_j, 1 ≤ i, j ≤ t, for which either i = j, or d_H(V_i, V_j) < d ₀, or the pair (V_i, V_j) is not ε-regular.

It is easy to see that the process above deletes at most edges, where the last inequality follows from our choice of constants. We claim the resulting subgraph H′ is triangle-free.

Suppose, on the contrary, that H′ contains a copy of with vertex set {v_h, v_i, v_j}, where, by construction of H′, we may assume v_h ∈ V_h, v_i ∈ V_i and v_j ∈ V_j, for 1 ≤ h < i < j ≤ t. Then, it must also be the case that each of (V_h, V_i), (V_i, V_j), and (V_h, V_j) are ε-regular with respective densities at least d ₀. Fact 10 then implies that the 3-partite subgraph H′[V_h, V_i, V_j] induced on V_h υ V_i υ V_j contains at least copies of , contradicting our hypothesis that H had at most ζn ³ such copies.

Regularity Method for Hypergraphs

Szemerédi's regularity lemma decomposes any given graph into pseudorandom blocks, the ε-regular pairs. This notion of pseudorandomness admits the companion counting statement in Fact 10. To develop a regularity method for hypergraphs, one needs a concept of pseudorandomness that allows one to prove both a regularity lemma (which decomposes any given hypergraph into pseudorandom blocks) and a counting lemma (which estimates the number of hypergraphs of a given isomorphism type in an appropriate collection of pseudorandom blocks).

Various concepts capturing the notion of pseudorandomness for hypergraphs have been studied; see Haviland and Thomason (26) and Chung and Graham (27–30). “Deviation,” the central concept in refs. 29 and 30, admits a companion counting statement, as does “discrepancy,” a different notion of pseudorandomness for hypergraphs, studied in ref. 31. No matching regularity lemma, however, is known for either deviation or discrepancy.

Before we introduce the notion of pseudorandomness to be employed, we note that, to extend Theorem 9 to hypergraphs, one also needs to establish a suitable concept of partition. Recall that in Theorem 9 the main structure that undergoes regularization is the edge set of a graph, and a certain partition of the vertex set is an auxiliary structure. Briefly, the 2-tuples (edges) are regularized versus the 1-tuples (vertices). If for k-graphs, k ≥ 3, we just regularize the k-tuples versus 1-tuples, as, e.g., in refs. 32–34, then the natural analogue to the counting lemma fails to be true (see ref. 35 for a counterexample).

A more refined approach is to consider an auxiliary partition of the j-tuples for each j < k. This idea was pursued in refs. 36 and 37 with no attempt, however, to prove a companion counting statement. Building on the ideas from ref. 37, Frankl and Rödl improved the concept of hypergraph regularity for k = 3 in ref. 15 and proved a corresponding regularity lemma for 3-graphs. They also succeeded in proving a companion counting lemma for the special case , the complete 3-graph on four vertices. Subsequently, the regularity lemma from ref. 15 was extended to k-graphs for arbitrary k ≥ 3 in ref. 16.

We shall now outline the regularity lemmas of refs. 15 and 16 and begin by fixing some notation. A k-uniform clique of order j, denoted by , is a k-graph on j ≥ k vertices consisting of all many k-tuples [i.e., is isomorphic to ].

Let l ≥ k ≥ 2 be fixed integers. For each integer 2 ≤ j < k, let be an l-partite j-graph with vertex partition . Let be the complete l-partite j-graph, and, for 2 ≤ i < j < k, let be the family of all j-element vertex sets that span the clique in .

For j ≥ 3, fix classes V_i1,..., V_ij,1 ≤ i ₁ < · · · < i_j ≤ l. For an integer r ≥ 1, let be a family of subhypergraphs of , the j-partite subgraph of induced on V_{i 1} υ · · · υ V_ij. We define the density or relative density of with respect to Q ^{(j - 1)} as if and 0 otherwise.

We are now in position to introduce a notion of pseudorandomness for j-graphs. For positive reals δ_j and d_j and integer r ≥ 1, we say that is (δ_j, d_j, r)-regular with respect to (w.r.t.) if for any choice of classes V_{i 1},..., V_ij, 1 ≤ i ₁ < · · · < i_j ≤ l, and any collection of subhypergraphs of satisfying we have This concept of regularity gives control over the structure of the hypergraph with respect to the hypergraph . To gain more control on the structure of , one imposes additional structural assumptions on . In ref. 16, it is assumed that is itself (δ_{j -1}, d_{j -1}, r)-regular w.r.t. some , which again is (δ_{j -2}, d_{j -2}, r)-regular w.r.t. some , etc.

The discussion above leads to the definition of an (l, h)-complex. For l ≥ h, an (l, h)-complex G is a system of l-partite j-graphs satisfying for 2 ≤ j ≤ h, with the same vertex partition . Given vectors of positive reals δ = (δ₂,..., δ_h) and d = (d ₂,..., d_h) and an integer r ≥ 1, we say that an (l, h)-complex G is (δ, d, r)-regular if

1. for each 1 ≤ i ₁ < i ₂ ≤ l, is δ₂-regular with density d ₂ ± δ₂;

2. for each 3 ≤ j ≤ h, is (δ_j, d_j, r)-regular with respect to .

Informally speaking, regular complexes are the pseudorandom blocks into which the hypergraph regularity lemma decomposes any large enough hypergraph.

We now proceed to describe the partition analogue of the hypergraph regularity lemma in ref. 16. To this end, we shall need the concept of a (μ, δ, d, r)-equitable family of partitions, which, as we shall see momentarily, is a sequence of partitions of vertices, pairs, triples,...,(k - 1)-tuples. Let μ > 0 be a real number, let δ = (δ₂,..., δ_{k -1}) and d = (d ₂,..., d_{k -1}) be vectors of positive reals, and let r ≥ 1 be an integer. Let a = (a ₁,..., a_{k -1}) be a vector of positive integers and V an n-element vertex set. We say that a family of partitions on V is (μ, δ, d, r)-equitable if it satisfies the following conditions:

1. (P1) is an equitable vertex partition of V, i.e., |V ₁| ≤ · · · ≤ |V_{a 1}| ≤ |V ₁| + 1,

2. (P2) partitions so that if and , then is partitioned into at most a_j parts, all of them members of , and, most importantly,

3. (P3) for all but at most μn^k k-tuples there is a unique (δ, d, r)-regular (k, k - 1)-complex such that has as members different partition classes from and .

The complex mentioned in (P3) takes the place of the pairs (V_i, V_j) in Theorem 9. We say that a k-graph is (δ_k, r)-regular w.r.t. a family of partitions 𝒫 if all but at most δ_kn^k edges K of have the property that and if is the unique (k, k - 1)-complex for which , then is -regular w.r.t. .

The hypergraph regularity lemma from ref. 16, stated below, asserts that for every k-graph there exists a (μ, δ, d, r)-equitable family of partitions 𝒫 with a bounded number of complexes so that is (δ_k, r)-regular w.r.t. 𝒫.

Theorem 11 (Hypergraph Regularity Lemma). For all positive reals μ and δ_k and functions there exist T ₀ and n ₀ so that the following holds. For every k-graph on n ≥ n ₀ vertices, there exist a family of partitions and a vector d = (d ₂,..., d_{k -1}) so that, for δ = (δ₂,..., δ_{k -1}), where δ_j = δ_j(d_j,..., d_{k -1}) for all j, and r = r(a ₁, d), the following holds:

1. 𝒫 is a (μ, δ, d, r)-equitable family of partitions and a_i ≤ T ₀ for every i = 1,..., k - 1 and

2. is (δ_k, r)-regular w.r.t. 𝒫.

In essence, this is similar to the regularity lemma for graphs, Theorem 9, and the regularity lemma for 3-graphs (15). For instance, for a graph G, Szemerédi's regularity lemma implies that most of the edges of G belong to ε-regular, bipartite subgraphs G[V_i, V_j]. In the above concept of hypergraph regularity, the (δ, d, r)-regular (k, k)-complexes correspond to the ε-regular pairs in Szemerédi's partition. More specifically, the auxiliary structure corresponds to the pairs of vertex sets (V_i, V_j), while corresponds to the edge set G[V_i, V_j] induced by V_i and V_j.)

Note that in Theorem 11, for each 2 ≤ j ≤ k - 1, the constant δ_j may be chosen as a function of d_j,..., d_{k -1}. Therefore, we may ensure δ_j << min{d_j,..., d_{k -1}}. However, we have no control over the relation between δ_j and d_{j -1}. In particular, Theorem 11 cannot avoid the outcome δ_j >> d_{j -1}, thus forcing us to face the following hierarchy concerning the constant δ_k and the constant entries of the vectors δ and d:

For a counting lemma for hypergraphs to be an appropriate counterpart of the regularity lemma in Theorem 11, it necessarily has to match the quantification stated in Eq. 1. Such a result has been obtained in ref. 17.

Theorem 12 (Hypergraph Counting Lemma). For all integers 2 ≤ k ≤ l the following holds: ∀γ > 0 ∀d_k > 0∃δ_k > 0 ∀d_{k -1} > 0∃δ_{k -1} > 0 · · · ∀d ₂ > 0∃δ₂ > 0 and there are integers r and m ₀ so that, with d = (d ₂,..., d_k), δ = (δ₂,..., δ_k) and m ≥ m ₀ , if is a (δ, d, r)-regular (l, k)-complex with vertex partition and |V_i| = m, then

Unlike the case of graphs (k = 2), Theorem 12 for k ≥ 3 was the most technical part of the approach outlined here. The proof of Theorem 12 establishes a reduction to a simpler counting problem, previously addressed in corollary 6.11 of ref. 31. The special case k = 3 of Theorem 12 has been considered by three of us (B.N., V.R., and M.S., unpublished data) following a similar but simpler approach.