HYPERGRAPHS, QUASI-RANDOMNESS, AND CONDITIONS FOR REGULARITY

YOSHIHARU KOHAYAKAWA, VOJTĚCH RÖDL, AND JOZEF SKOKAN

Dedicated to Professors Vera T. Sós and András Hajnal on the occasion of their 70th birthdays

Abstract. Haviland and Thomason and Chung and Graham were the first to investigate systematically some properties of quasi-random hypergraphs. In particular, in a series of articles, Chung and Graham considered several quite disparate properties of random-like hypergraphs of density 1/2 and proved that they are in fact equivalent. The central concept in their work turned out to be the so called deviation of a hypergraph. They proved that having small deviation is equivalent to a variety of other properties that describe quasi-randomness. In this paper, we consider the concept of discrepancy for k-uniform hypergraphs with an arbitrary constant density d (0 < d < 1) and prove that the condition of having asymptotically vanishing discrepancy is equivalent to several other quasi-random properties of H, similar to the ones introduced by Chung and Graham. In particular, we prove that the correct ‘spectrum’ of the s-vertex subhypergraphs is equivalent to quasi-randomness for any s ≥ 2k. Our work may be viewed as a continuation of the work of Chung and Graham, although our proof techniques are different in certain important parts.

1. Introduction and the main result

The rich interplay between the investigation of deterministic combinatorial structures and random combinatorial structures has been an important feature of modern combinatorics. One aspect of this interaction focuses on the study of deterministic structures that ‘mimic’ the behavior of random ones, from certain specific points of view.

In this paper, we are interested in ‘quasi-random’ hypergraphs, in the sense of Chung and Graham [5, 6]. Haviland and Thomason [9, 10], Chung [4], and Chung and Graham [5, 6] have already established the fundamental results in this area. Babai, Nisan, and Szegedy [3] have implicitly found a connection between communication complexity and what is known as ‘hypergraph discrepancy’, a key concept, as we shall see, in the study of quasi-random hypergraphs. This connection was explored further by Chung and Tetali [7]. Here, we carry out our investigation very much along the lines of Chung and Graham [5, 6], except that we focus on

Date: June 28, 2001. The first author was partially supported by FAPESP (Proc. 96/04505–2), by CNPq

(Proc. 910064/99–7, 468516/00–0, and 300334/93–1), and by MCT/CNPq (PRONEX project 107/97). The second author was partially supported by NSF grants DMS-9704114, DMS-0071261 and INT-0072064. The third author was partially supported by NSF grant INT-0072064.

The authors are grateful to the referee for his or her comments.

hypergraphs of arbitrary constant density, making use of different techniques in certain delicate parts.

In the remainder of this introduction, we carefully discuss a result of Chung and Graham [5] and state our main result, Theorem 1.3 below.

1.1. The result of Chung and Graham. We need to start with some definitions. For a set V and an integer k ≥ 2, let [V]^{k} denote the system of all k-element subsets of V. A subset G ⊂ [V]^{k} is called a k-uniform hypergraph. If k = 2, we have a graph. We sometimes use the notation G = (V (G), E(G)). If there is no danger of confusion, we shall identify the hypergraphs with their edge sets. In particular, we write |H| for the number of edges in H. Throughout this paper, the integer k is assumed to be a fixed constant.

For any l-uniform hypergraph G and k ≥ l, let K_{k}(G) be the set of all k-element sets that span a clique K_{k}^{(l)} on k vertices. We also denote by K_{k}(2) the complete k-partite k-uniform hypergraph whose every partite set contains precisely two vertices. We refer to K_{k}(2) as the generalized octahedron, or, simply, the octahedron.

We also consider a function μ_{H}: [V]^{k} → {−1, 1} such that, for all e ∈ [V]^{k}, we have

μ_{H}(e) = \{ \begin{matrix}−1, & if e ∈ H \\ 1, & if e ∉ H. \end{matrix}

Let [k] = {1, 2, …, k} and let V^{2k} denote the set of all 2k-tuples (v_{1}, v_{2}, …, v_{2k}), where v_{i} ∈ V (1 ≤ i ≤ 2k). Furthermore, let Π_{H}^{(k)} : V^{2k} → {−1, 1} be given by

Π_{H}^{(k)}(u_{1}, …, u_{k}, v_{1}, …, v_{k}) = ∏_{ε=(ε_{i})_{i=1}^{k}} μ_{H}(ε_{1}, …, ε_{k}),

where the product is over all vectors ε = (ε_{i})_{i=1}^{k} with ε_{i} ∈ {u_{i}, v_{i}} for all i and we understand μ_{H} to be 1 on arguments with repeated entries.

The deviation dev(H) of H is defined by

dev(H) = \frac{1}{m^{2k}} ∑_{u_{i},v_{i}∈V, i∈[k]} Π_{H}^{(k)}(u_{1}, …, u_{k}, v_{1}, …, v_{k}).

Note that the quantity m^{2k} dev(H) is essentially the difference between the number of 2k-tuples that induce an even number of edges and the number of 2k-tuples that induce an odd number of edges.

For two hypergraphs G and H, we denote by \binom{H}{G} the set of all induced subhypergraphs of H that are isomorphic to G. We also write \binom{H}{G}^{w} for the number of weak (i.e., not necessarily induced) subhypergraphs of H that are isomorphic to G. Furthermore, we need the notion of the link of a vertex.

Definition 1.1. Let H be a k-uniform hypergraph and x ∈ V (H). We shall call the (k − 1)-uniform hypergraph

H(x) = {e \ {x}: e ∈ H, x ∈ e}

the link of the vertex x in H. For a subset W ⊂ V (H), we define H(W) by

H(W) = ⋂_{x∈W} H(x).

For simplicity, if W = {x_{1}, …, x_{k}}, we write H(x_{1}, …, x_{k}).

Observe that if H is k-partite, then H(x) is (k − 1)-partite for every x ∈ V. Furthermore, if k = 2, then H(x) may be identified with the set of all vertices connected to x, i.e., H(x) is the neighborhood of x; furthermore, H(x, x′) is the set of all vertices connected to both x and x′, i.e., H(x, x′) is the ‘joint neighborhood’ of x and x′.

In [5], Chung and Graham proved that if the density of an m-vertex k-uniform hypergraph H is 1/2, i.e., |H| = (1/2 + o(1))\binom{m}{k}, where o(1) → 0 as m → ∞, then the following statements are equivalent:

Q_{1}(s): for all k-uniform hypergraphs G on s ≥ 2k vertices and automorphism group Aut(G),

|\binom{H}{G}| = (1 + o(1))\binom{m}{s}2^{−\binom{s}{k}} \frac{s!}{| Aut(G)|},

Q_{2}: for all k-uniform hypergraphs G on 2k vertices and automorphism group Aut(G),

|\binom{H}{G}| = (1 + o(1))\binom{m}{2k}2^{−\binom{2k}{k}} \frac{(2k)!}{| Aut(G)|},

Q_{3}: dev(H) = o(1),

Q_{4}: for almost all choices of x, y ∈ V, the (k − 1)-uniform hypergraph \overline{H(x)△H(y)}, that is, the complement [V]^{k−1} \ (H(x)△H(y)) of the symmetric difference of H(x) and H(y), satisfies Q_{2} with k replaced by k − 1,

Q_{5}: for k − 1 ≤ r < 2k and almost all x, y ∈ V,

|\binom{H(x, y)}{K_{r}^{(k−1)}}| = (1 + o(1))\binom{m}{r}2^{−\binom{r}{k−1}}.

The equivalence of these properties is understood in the following sense. For two properties involving o(1) terms P = P (o(1)) and P′ = P′(o(1)), the implication “P ⇒ P′” means that for every ε > 0 there is a δ > 0 so that any k-uniform hypergraph H on m vertices satisfying P (δ) must also satisfy P′(ε), provided m > M_{0}(ε).

Chung and Graham [5] stated that “it would be profitable to explore quasirandomness extended to simulating random k-uniform hypergraphs G_{p}(n) for p ≠ 1/2, or, more generally, for p = p(n), especially along the lines carried out so fruitfully by Thomason [12, 13].” Our present aim is to take the first steps in this direction. In this paper, we concentrate on the case in which p is an arbitrary constant. In certain crucial parts, our methods are different from the ones of Chung and Graham. In fact, it seems to us that the fact that the density of H is 1/2 is essential in certain proofs in [5] (especially those involving the concept of deviation).

1.2. Discrepancy and the subgraph counting formula. The following concept was proposed by Frankl and Rödl and was later used by Chung [4] and Chung and Graham in [5, 6]. For an m-vertex k-uniform hypergraph H with vertex set V, we define the density d(H) and the discrepancy disc_{1/2}(H) of H as follows:

d(H) = |H|\binom{m}{k}^{−1}

and

disc_{1/2}(H) = \frac{1}{m^{k}} max_{G⊂[V]^{k−1}} ||H ∩ K_{k}(G)| − |H̄ ∩ K_{k}(G)|| ,  (1)

where the maximum is taken over all (k − 1)-uniform hypergraphs G with vertex set V, and H̄ is the complement [V]^{k} \ H of H.

To accommodate arbitrary densities, we extend the latter concept as follows.

Definition 1.2. Let H be a k-uniform hypergraph with vertex set V with |V | = m. We define the discrepancy disc(H) of H as follows:

disc(H) = \frac{1}{m^{k}} max_{G⊂[V]^{k−1}} ||H ∩ K_{k}(G)| − d(H)|K_{k}(G)||,  (2)

where the maximum is taken over all (k − 1)-uniform hypergraphs G with vertex set V.

Observe that if d(H) = 1/2, then disc(H) = (1/2) disc_{1/2}(H), so both notions are equivalent. Following some initial considerations by Frankl and Rödl, Chung and Graham investigated the relation between discrepancy and deviation. In fact, Chung [4] succeeded in proving the following inequalities closely connecting these quantities:

(i) dev(H) < 4^{k}(disc_{1/2}(H))^{1/2^{k}}, (ii) disc_{1/2}(H) < (dev(H))^{1/2^{k}}.

For simplicity, we state the inequalities for the density 1/2 case. For the general case, see Section 5 of [4].

Before we proceed, we need to introduce a new concept. If the vertex set of a hypergraph is totally ordered, we say that we have an ordered hypergraph. Given two ordered hypergraphs G_{≺} and H_{≺′}, where ≺ and ≺′ denote the orderings on the vertex sets of G = G_{≺} and H = H_{≺′}, we say that a function f: V (G) → V (H) is an embedding of ordered hypergraphs if (i) it is an injection, (ii) it respects the orderings, i.e., f(x) ≺′ f(y) whenever x ≺ y, and (iii) f(g) ∈ H if and only if g ∈ G, where f(g) is the set formed by the images of all the vertices in g. Furthermore, if G = G_{≺} and H = H_{≺′}, we write

\binom{H}{G}_{≺} = \binom{H_{≺′}}{G_{≺}}

for the number of such embeddings. We use the same symbol ‘≺’ for the orders involved in case this causes no confusion.

As our main result, we shall prove the following extension of Chung and Graham’s result (in the sense that the density of H is allowed to be different from 1/2).

Theorem 1.3. Let H = (V, E) be a k-uniform hypergraph of density d on m vertices. Then the following statements are equivalent:

P_{1}: disc(H) = o(1),

P_{2}: disc(H(x)) = o(1) and d(H(x)) = (1 + o(1))d for all but o(m) vertices x ∈ V and disc(H(x, y)) = o(1) and d(H(x, y)) = (1 + o(1))d^{2} for all but o(m^{2}) pairs x, y ∈ V,

P_{3}: disc(H(x, y)) = o(1) and d(H(x, y)) = (1+o(1))d^{2} for all but o(m^{2}) pairs

x, y ∈ V, P_{4}: the number of non-induced copies of K_{k}(2) in H is asymptotically mini-

mized among all k-uniform hypergraphs of density d; indeed,

|\binom{H}{K_{k}(2)}^{w}| = (1 + o(1))\frac{m^{2k}}{2^{k}k!}d^{2^{k}},  (3)

P_{5}: for every s ≥ 2k and all k-uniform hypergraphs G on s vertices with e(G) edges and automorphism group Aut(G),

|\binom{H}{G}| = (1 + o(1))\binom{m}{s}d^{e(G)}(1 − d)^{\binom{s}{k}−e(G)} \frac{s!}{| Aut(G)|},

P′_{5}: for every ordering H_{≺′} of H and for every fixed integer s ≥ 2k, every ordered k-uniform hypergraph G_{≺} on s vertices with e(G) edges is such that

|\binom{H}{G}_{≺}| = (1 + o(1))\binom{m}{s}d^{e(G)}(1 − d)^{\binom{s}{k}−e(G)},

P_{6}: for all k-uniform hypergraphs G on 2k vertices with e(G) edges and automorphism group Aut(G),

|\binom{H}{G}| = (1 + o(1))\binom{m}{2k}d^{e(G)}(1 − d)^{\binom{2k}{k}−e(G)} \frac{(2k)!}{| Aut(G)|}.

P′_{6}: for every ordering H_{≺′} of H, every ordered k-uniform hypergraph G_{≺} on 2k vertices with e(G) edges is such that

|\binom{H}{G}_{≺}| = (1 + o(1))\binom{m}{2k}d^{e(G)}(1 − d)^{\binom{2k}{k}−e(G)}.

The equivalence between properties is understood in the sense of Chung and Graham’s approach.

Note that, similarly to the case where k = 2 (see, e.g., [1, 2]), the equivalence among the above properties may be used to develop a fast algorithm for checking whether a given hypergraph is quasi-random. While it is hard to check whether disc(H) ≤ δ directly from the definition of disc(H), one may check property P_{4} in O(m^{2k}) time. This may be further improved using techniques from [1, 11].

Some of the implications in Theorem 1.3 are fairly easy or are by now quite standard. There are, however, two implications that appear to be quite difficult.

The proof of Chung and Graham that dev_{1/2}(H) = o(1) implies P_{5} (the ‘subgraph counting formula’) is based on an approach that has its roots in a seminal paper of Wilson [14]. This beautiful proof seems to make non-trivial use of the fact that d(H) = 1/2. Our proof of the implication that small discrepancy implies the subgraph counting formula (P_{1} ⇒ P′_{5}) is based on a different technique, which works well in the arbitrary constant density case (see Section 6).

The second implication with a rather technical proof is P_{2} ⇒ P_{1}. This proof is based on the observation that in k-uniform k-partite hypergraphs the regularity of links and pair-links implies the regularity of the whole hypergraph. For details, we refer the reader to Sections 3.1 and 4.

Remark. Let us make some remarks on the asymptotic notation that we shall use. Unless otherwise stated, we understand by o(1) a function approaching zero as the number of vertices of a given hypergraph goes to infinity. We also use x ∼ y if x = (1 + o(1))y and x ≳ y if x ≥ (1 + o(1))y. Finally, we write O_{1}(x) for a term y such that |y| ≤ x.

2. Definitions

Besides introducing some definitions and notation, our aim in this section is to argue that, for most of the purposes of this paper, we may restrict ourselves to the case of k-partite k-uniform hypergraphs. To this end, we first set up a few facts concerning k-partite hypergraphs.

2.1. Definitions for partite hypergraphs. For simplicity, we first introduce the term cylinder to mean partite hypergraphs.

Definition 2.1. Let k ≥ l ≥ 2 be two integers. We shall refer to any k-partite l-uniform hypergraph H = (V_{1} ∪ ⋯ ∪ V_{k}, E) as a k-partite l-cylinder or (k, l)- cylinder. If l = k − 1, we shall often write H_{i} for the subhypergraph of H induced on ⋃_{j≠i} V_{j}. Clearly, H = ⋃_{i=1}^{k} H_{i}. We shall also denote by K_{k}^{(l)}(V_{1}, …, V_{k}) the complete (k, l)-cylinder with vertex partition V_{1} ∪ ⋯ ∪ V_{k}.

Definition 2.2. For a (k, l)-cylinder H, we shall denote by K_{j}(H), l ≤ j ≤ k, the (k, j)-cylinder whose edges are precisely those j-element subsets of V (H) that span cliques of order j in H.

Clearly, the quantity |K_{j}(H)| counts the total number of cliques of order j in H. In the case in which l = 1, the (k, j)-cylinder K_{j}(H) is the complete k-partite j-uniform hypergraph on ⋃ H = ⋃_{h∈H} h.

When we deal with cylinders, we have to measure density according to their natural vertex partitions.

Definition 2.3. Let H be a (k, k)-cylinder with k-partition V = V_{1} ∪ ⋯ ∪ V_{k}. We define the k-partite density or simply the density d(H) of H by

d(H) = \frac{|H|}{|V_{1}| … |V_{k}|}.

To be precise, we should have a distinguished piece of notation for the notion of k-partite density. However, the context will always make it clear which notion we mean when we talk about the density of a (k, k)-cylinder.

We should also be careful when we talk about the discrepancy of a cylinder.

Definition 2.4. Let H be a (k, k)-cylinder with vertex set V = V_{1} ∪ ⋯ ∪ V_{k}. We define the discrepancy disc(H) of H as follows:

disc(H) = \frac{1}{|V_{1}| … |V_{k}|} max_{G⊂[V]^{k−1}} ||H ∩ K_{k}(G)| − d(H)|K_{k}(G)||,  (4)

where the maximum is taken over all (k, k − 1)-cylinders G with vertex set V = V_{1} ∪ ⋯ ∪ V_{k}.

We now introduce a simple but important concept concerning the “regularity” of a (k, k)-cylinder.

Definition 2.5. Let H be a (k, k)-cylinder with k-partition V = V_{1} ∪ ⋯ ∪ V_{k} and let δ < α be two positive real numbers. We say that H is (δ, α)-regular if the following condition is satisfied: if G is any (k, k − 1)-cylinder such that

|K_{k}(G)| ≥ δ|V_{1}| … |V_{k}|,  (5)

then

(α − δ)|K_{k}(G)| ≤ |H ∩ K_{k}(G)| ≤ (α + δ)|K_{k}(G)|.  (6)

One should observe that the (δ, α)-regularity of a hypergraph H does not imply that H has density α; we may only conclude that the density of a (δ, α)-regular hypergraph is between α − δ and α + δ. Moreover, the following simple facts hold.

Fact 2.6. Let H be a (δ, α)-regular (k, k)-cylinder. Then disc(H) ≤ 2δ.

Fact 2.7. Suppose H is a (k, k)-cylinder with k-partition V = V_{1} ∪ ⋯ ∪ V_{k}. Put α = d(H) and assume that disc(H) ≤ δ. Then H is (δ^{1/2}, α)-regular.

2.2. The k-partite reduction. Suppose H is a k-uniform hypergraph and let H′ be one of its k-partite spanning subhypergraphs. In this section, we try to relate the deviation and the discrepancy of H′ to those of H.

Definition 2.8. Let H = (V, E) be a k-uniform hypergraph with m vertices and let P = (V_{i})_{1}^{k} be a partition of the vertex set V. We denote by H_{P} the (k, k)-cylinder consisting of the edges h ∈ H satisfying |h ∩ V_{i}| = 1 for all i ∈ [k].

The following proposition holds.

Proposition 2.9. For any partition P = (V_{i})_{1}^{k} of V, we have (i) disc(H) ≥ |d(H_{P}) − d(H)||V_{1}| … |V_{k}|/m^{k}, and (ii) disc(H_{P}) ≤ 2 disc(H)m^{k}/|V_{1}| … |V_{k}|.

Proof. Let P = (V_{i})_{1}^{k} be any partition of V. Observe that H_{P} consists precisely of the vertex sets of those copies of K_{k}^{(k−1)} in K = K_{k}^{(k−1)}(V_{1}, …, V_{k}) which are also edges in H; that is, H_{P} = H∩K_{k}(K). Since |K_{k}(K)| = |K_{k}(K_{k}^{(k−1)}(V_{1}, …, V_{k}))| = |V_{1}| … |V_{k}|, this implies the first part of the proposition by taking G = K in (2).

On the other hand, let G_{0} ⊂ [V]^{k−1} be a (k, k − 1)-cylinder for which the maximum is attained in (4), the definition of disc(H_{P}). Observe that H_{P} ∩ K_{k}(G_{0}) = H ∩ K_{k}(G_{0}). Then

disc(H_{P}) = \frac{1}{|V_{1}| … |V_{k}|}||H_{P} ∩ K_{k}(G_{0})| − d(H_{P})|K_{k}(G_{0})||

≤ \frac{1}{|V_{1}| … |V_{k}|}||H ∩ K_{k}(G_{0})| − d(H)|K_{k}(G_{0})||

+ \frac{1}{|V_{1}| … |V_{k}|}|d(H)|K_{k}(G_{0})| − d(H_{P})|K_{k}(G_{0})||

≤ \frac{m^{k}}{|V_{1}| … |V_{k}|} disc(H) + \frac{1}{|V_{1}| … |V_{k}|}|K_{k}(G_{0})| |d(H) − d(H_{P})|

≤ \frac{m^{k}}{|V_{1}| … |V_{k}|} disc(H) + |d(H) − d(H_{P})|

≤ \frac{2m^{k}}{|V_{1}| … |V_{k}|} disc(H),

where in the last inequality we used (i). □

We shall also need the following fact, which follows easily from, say, Chebyshev’s inequality.

Fact 2.10. Let H = (V, E) be an m-vertex k-uniform hypergraph. Then (1 − o(1))k^{m} partitions P = (V_{i})_{1}^{k} of V satisfy

(i) |V_{i}| = (1 + o(1))m/k for all i ∈ [k],

(ii) |H_{P}| = (1 + o(1))(k!/k^{k})|H|, and (iii) d(H_{P}) = (1 + o(1))d(H),

where o(1) → 0 as |H|/m^{k−1} → ∞.

An immediate consequence of the previous proposition and Fact 2.10 is the following.

Claim 2.11. If disc(H) = o(1), then disc(H_{P}) = o(1) for (1 − o(1))k^{m} partitions P = (V_{i})_{1}^{k} of V.

With some more effort, one may prove a converse to Claim 2.11.

Claim 2.12. Suppose there exists a positive real number γ > 0 such that disc(H_{P}) = o(1) for γk^{m} partitions P = (V_{i})_{1}^{k} of V. Then disc(H) = o(1).

Proof. Let S be a set of partitions P for which disc(H_{P}) = o(1) and |S| ≥ γk^{m}. Suppose disc(H) ≥ δ for some fixed δ > 0, and let G_{0} be a (k − 1)-uniform hypergraph for which the maximum is attained in (2), the definition of disc(H). Let P = (V_{i})_{1}^{k} ∈ S be a partition satisfying the conclusion of Fact 2.10 with respect to H, H∩K_{k}(G_{0}), and K_{k}(G_{0}). Such a partition must exist since γk^{m} +(1−o(1))k^{m} > k^{m}. Observe that, then,

|H_{P} ∩ K_{k}(G_{0})| = |(H ∩ K_{k}(G_{0}))_{P}| = (1 + o(1))\frac{k!}{k^{k}} |H ∩ K_{k}(G_{0})|,

and

|K_{k}(G_{0} ∩ K_{k}^{(k−1)}(V_{1}, …, V_{k}))| = |(K_{k}(G_{0}))_{P}| = (1 + o(1))\frac{k!}{k^{k}} |K_{k}(G_{0})|,

and, from (iii) of Fact 2.10,

d(H_{P}) = (1 + o(1))d(H).

For convenience, put K = K_{k}^{(k−1)}(V_{1}, …, V_{k}). We use an approach similar to the one in Proposition 2.9 to get

disc(H) = \frac{1}{m^{k}} ||H ∩ K_{k}(G_{0})| − d(H)|K_{k}(G_{0})||

= \frac{1}{m^{k}} |(1 + o(1))\frac{k^{k}}{k!} |H_{P} ∩ K_{k}(G_{0})| − (1 + o(1))d(H_{P})\frac{k^{k}}{k!} |K_{k}(G_{0} ∩ K)||

≤ \frac{1}{m^{k}} \frac{k^{k}}{k!} ||H_{P} ∩ K_{k}(K ∩ G_{0})| − d(H_{P})|K_{k}(G_{0} ∩ K)||

+ \frac{1}{m^{k}} \frac{k^{k}}{k!} o(1) (|H_{P} ∩ K_{k}(K ∩ G_{0})| + d(H_{P})|K_{k}(G_{0} ∩ K)|)

≤ (1 + o(1))\frac{1}{k!} disc(H_{P}) + \frac{1}{m^{k}} \frac{k^{k}}{k!} o(1)2\binom{m}{k} ≤ \frac{2}{k!} disc(H_{P}) + \frac{2k^{k}}{(k!)^{2}} o(1).

Since by our assumptions disc(H_{P}) = o(1), we immediately obtain that disc(H) < δ for large enough m, which is a contradiction. □

We now state the k-partite version of a part of our main result, Theorem 1.3.

Theorem 2.13. Suppose V = V_{1} ∪ ⋯ ∪ V_{k}, |V_{1}| = ⋯ = |V_{k}| = n, and let H = (V, E) be a (k, k)-cylinder with |H| = dn^{k}. Then the following four conditions are equivalent:

C_{1}: H is (o(1), d)-regular;

C_{2}: H(x) is (o(1), d)-regular for all but o(n) vertices x ∈ V_{k} and H(x, y) is

(o(1), d^{2})-regular for all but o(n^{2}) pairs x, y ∈ V_{k}; C_{3}: H(x, y) is (o(1), d^{2})-regular for all but o(n^{2}) pairs x, y ∈ V_{k}; C_{4}: the number of copies of K_{k}(2) in H is asymptotically minimized among all such (k, k)-cylinders of density d, and equals (1 + o(1))n^{2k}d^{2^{k}}/2^{k}.

Remark. The simplifying condition |V_{1}| = ⋯ = |V_{k}| = n has the sole purpose of making the proof more readable and transparent. The immediate generalization of Theorem 2.13 for V_{1}, …, V_{k} of arbitrary sizes holds.

The proof of Theorem 2.13 will be given in Sections 4 and 5.

3. The derivation of the general case

In this part, we prove Theorem 1.3. We divide this proof into five sections. In Section 3.1, we show the equivalence of properties P_{1}, P_{2}, and P_{3}. The proof of P_{4} ⇒ P_{1} is in Section 3.2. Both sections use Theorem 2.13 as the main tool. In Section 3.3, we prove P_{1} ⇒ P′_{5} using the ‘subhypergraph counting formula’ from Section 6. Then we show that P′_{5} ⇒ P_{5} ⇒ P_{6} and P′_{5} ⇒ P′_{6} ⇒ P_{6} (see Section 3.4). Finally, we prove P_{6} ⇒ P_{4} in Section 3.5. The flow of the whole proof is described in the following diagram.

P_{2} ⇒ P_{3} ⇒ P_{1}
⇑  ⇓
P_{1}  P′_{6} ⇐ P′_{5}
⇑ ⇓ ⇓
P_{4} ⇐ P_{6} ⇐ P_{5}

3.1. Proof of P_{1} ⇔ P_{2} ⇔ P_{3}. We are now ready to show that, in the first part of the proof of Theorem 1.3, we may assume the hypergraph H to be k-partite. To be more precise, we show that the equivalence P_{1} ⇔ P_{2} ⇔ P_{3} in Theorem 1.3 follows from Theorem 2.13. We shall illustrate this on P_{1} ⇒ P_{2}; the other implications are handled similarly. In fact, we shall be somewhat sketchy; we shall only indicate the double counting argument that gives this result.

Suppose that we have a k-uniform hypergraph H with density d such that disc(H) = o(1). From Fact 2.10 and Claim 2.11 we know that for all but o(1)k^{m} partitions P of V we have disc(H_{P}) = o(1) and d(H_{P}) = (1 + o(1))d. For every partition P, denote by X(P) the set of all vertices x ∈ V such that either disc(H_{P}(x)) ≠ o(1) or disc(H_{P}) ≠ o(1). From Theorem 2.13 and Facts 2.6 and 2.7, we know that for all but o(1)k^{m} partitions P, we have |X(P)| = o(m). For the remaining o(1)k^{m} partitions P, we use |X(P)| ≤ m. For a vertex x ∈ V, we define P(x) to be the collection of all partitions P for which x ∈ X(P). One can easily see that

∑_{P} |X(P)| = ∑_{x∈V} |P(x)|.

Let S be the set of vertices x ∈ V for which |P(x)| > (1/2)k^{m}. Then

o(1)k^{m}m + o(m)k^{m} ≥ ∑_{P} |X(P)| = ∑_{x∈V} |P(x)| > \frac{1}{2}|S|k^{m},

hence |S| = o(m). This means that, for almost all vertices x ∈ V, we have disc(H(x)_{P}) = disc(H_{P}(x)) = o(1) for at least (1/2)k^{m} partitions P. By Claim 2.12, it follows that disc(H(x)) = o(1) for all but o(m) vertices x ∈ V. We proceed similarly in order to show that disc(H(x, y)) = o(1) for all but o(m^{2}) pairs x, y ∈ V.

3.2. The minimization of the number of octahedra. The aim of this section is to show that property P_{1} can be derived from property P_{4} using the equivalence of the k-partite properties C_{1} and C_{4}. We start with the following lemma.

Lemma 3.1. Suppose a k-uniform hypergraph H on m vertices with density d = d(H) is such that

|\binom{H}{K_{k}(2)}^{w}| ∼ \frac{m^{2k}}{2^{k}k!}d^{2^{k}}.  (7)

Then, for almost all partitions P of V = V (H),

|\binom{H_{P}}{K_{k}(2)}^{w}| ∼ \frac{n^{2k}}{2^{k}} d^{2^{k}}  (8)

holds for n = m/k.

Proof. Put

X(P) = |\binom{H_{P}}{K_{k}(2)}^{w}| .

We consider X as a r.v. on the uniform probability space of all partitions P of the vertex set V of H. Clearly, we may write X as a sum of 0–1 indicator random variables as follows:

X = ∑_{K} X_{K},

where the sum is over all K ⊂ H with K ≅ K_{k}(2) and X_{K}(P) = 1 if and only if K ⊂ H_{P}. Note that ℙ(X_{K} = 1) = ℙ(K ⊂ H_{P}) = k!k^{m−2k}/k^{m}. Therefore, using (7), we have

𝔼(X) = ∑_{K} 𝔼(X_{K}) = ∑_{K} ℙ(X_{K} = 1) ∼ \frac{m^{2k}}{2^{k}k!}d^{2^{k}} \frac{k!k^{m−2k}}{k^{m}} ∼ \frac{n^{2k}}{2^{k}} d^{2^{k}}. (9)

We now invoke a lemma that will be proved in Section 5.1. Indeed, Claim 5.2 states that

|\binom{G}{K_{k}(2)}^{w}| ≳ \frac{n^{2k}}{2^{k}} d^{2^{k}}  (10)

for all (k, k)-cylinders G of density d with n vertices in each of its vertex classes. Comparing (9) and (10), we deduce that the expectation of X is asymptotically equal to min X, and hence

ℙ (X ≥ (1 + η)\frac{n^{2k}}{2^{k}} d^{2^{k}}) = o(1)

for any fixed η > 0. This completes the proof of Lemma 3.1.

□

We turn to the proof of the implication P_{4} ⇒ P_{1}.

Proof of P_{4} ⇒ P_{1}. Let H be a k-uniform hypergraph on m vertices such that

|\binom{H}{K_{k}(2)}^{w}| ∼ \frac{m^{2k}}{2^{k}k!}d^{2^{k}},  (11)

where d is the density d(H) of H. Lemma 3.1 then implies that almost all vertex partitions P = (V_{i})_{1}^{k} are such that

|\binom{H_{P}}{K_{k}(2)}^{w}| ∼ \frac{n^{2k}}{2^{k}} d^{2^{k}},

where n = m/k. The implication C_{4} ⇒ C_{1} of Theorem 2.13 gives that, then, the (k, k)-cylinder H_{P} is (o(1), d(H_{P}))-regular for almost all P. We now use Fact 2.6 to conclude that H_{P} satisfies disc(H_{P}) = o(1) for a.a. P. We may then apply Claim 2.12 with, say, γ = 1/2, to deduce that disc(H) = o(1); in other words, property P_{1} holds for H. □

3.3. Proof of P_{1} ⇒ P′_{5}. In this section, we prove that any k-uniform hypergraph H with disc(H) = o(1) must be such that any k-uniform hypergraph G on s vertices must occur as an induced subhypergraph of H as many times as one would expect if H were a truly random hypergraph with density d. Our proof will be based on a certain technical result, the ‘subhypergraph counting formula’, which will be proved in Section 6.

Proof of P_{1} ⇒ P′_{5}. We need to show that for every given integer s ≥ 2k, real number ε > 0, and density d ∈ (0, 1), there exists a real number δ > 0 such that property P_{1}(δ) (i.e., property P_{1} with o(1) replaced by δ) implies property P′_{5}(ε, s) (i.e., property P′_{5} with given s and o(1) replaced by O_{1}(ε)).

Let δ_{0} = δ_{0}(d, ε) be the positive real number determined by Corollary 6.13 and d_{0} = min{d, 1 − d}. Choose δ > 0 of the form 1/t^{2k}, where t ∈ ℕ, satisfying

δ = \frac{1}{t^{2k}} ≤ (\frac{δ_{0}}{2} )^{4} ,  (12a)

and

δ^{1/2k} = \frac{1}{t} ≤ \frac{εd\binom{s}{k}_{0}}{100s^{2}} ≤ \frac{1}{s}.  (12b)

Let m ≥ m(d, ε) be an integer divisible by t and set n = m/t.

Suppose that H = H_{≺′} and G = G_{≺} are two ordered k-uniform hypergraphs such that V (H) = {v_{1} ≺′ v_{2} ≺′ ⋯ ≺′ v_{m}}, V (G) = {w_{1} ≺ w_{2} ≺ ⋯ ≺ w_{s}}, d(H) = d, and disc(H) ≤ δ.

For every i ∈ [t] set V_{i} = {v_{j+n(i−1)} : j ∈ [n]} and note that V (H) = ⋃_{i=1}^{t} V_{i} is a partition of V (H). An s-tuple {u_{1}, …, u_{s}} is crossing, or transversal, if |{u_{1}, …, u_{s}} ∩ V_{i}| ≤ 1 for all i ∈ [t]. Note that the number of non-crossing stuples is bounded from above by

t\binom{n}{2}\binom{m − 2}{s − 2} = \frac{1}{2}m (\frac{m}{t} − 1) \binom{m − 2}{s − 2}\frac{(s)_{2}}{(s)_{2}}

= \frac{m(m − t)}{t(m)_{2}} \binom{s}{2}\binom{m − 2}{s − 2}\frac{(m)_{2}}{(s)_{2}} ≤ \frac{1}{t}\binom{s}{2}\binom{m}{s}.

Since the number of crossing s-tuples is \binom{t}{s}n^{s}, we have the following fact.

Fact 3.2. \binom{m}{s} − \binom{t}{s}n^{s} ≤ \binom{s}{2}\binom{m}{s}/t.

For I ⊂ [t], put H_{I} = H [⋃_{i∈I} V_{i}] and observe that H_{I} is an (|I|, k)-cylinder. One can mimic the proof of Proposition 2.9 and obtain the following fact.

Fact 3.3. For every I ∈ [t]^{k}, we have d(H_{I}) = d + O_{1}(δ^{1/2}) and

disc(H_{I}) ≤ 2δ × t^{k} = 2δ^{1/2}.

Consequently, owing to Fact 2.7, the cylinder H_{I} is (2δ^{1/4}, d)-regular.

Thus, the (s, k)-cylinder H_{I} satisfies the assumptions of Corollary 6.13 for every I ∈ [t]^{s}. Therefore, there exist (1 + O_{1}(ε))d^{e(G)}(1 − d)^{\binom{s}{k}−e(G)}n^{s} transversal copies of G in each H_{I} (I ∈ [t]^{s}).

Let I = {i_{1} < i_{2} < ⋯ < i_{s}} ∈ [t]^{s} and consider one transversal copy of G in H on vertices u_{1} ≺ u_{2} ≺ ⋯ ≺ u_{s}, where u_{j} ∈ V_{i_{j}} for every j ∈ [s]. Then the mapping φ: V (G) → V (H) defined by φ(w_{i}) = u_{i} (i ∈ [s]) is an injection preserving order, and preserving edges and non-edges of G; thus, φ ∈ \binom{H}{G}_{≺}. In view of the previous paragraph, we have

(1 + O_{1}(ε))d^{e(G)}(1 − d)^{\binom{s}{k}−e(G)}n^{s} × \binom{t}{s}  (13)

such mappings.

On the other hand, let φ ∈ \binom{H}{G}_{≺}. The s-tuple \{φ(w_{1}) ≺′ φ(w_{2}) ≺′ ⋯ ≺′ φ(w_{s})\} is either crossing or not.

In the first case, this s-tuple induces a transversal copy of G in H, and, therefore, equation (13) yields the number of mappings φ for which this case occurs. In the second case, {φ(w_{1}) ≺′ φ(w_{2}) ≺′ ⋯ ≺′ φ(w_{s})} is not crossing. By Fact 3.2, there are at most \binom{s}{2}\binom{m}{s}/t mappings φ yielding this case.

Combining these two cases together implies that

|\binom{H}{G}_{≺}| = (1 + O_{1}(ε))d^{e(G)}(1 − d)^{\binom{s}{k}−e(G)}n^{s} × \binom{t}{s} + O_{1} (\frac{1}{t}\binom{s}{2}\binom{m}{s}) .

To complete the proof, it suffices to show that

(1 + O_{1}(ε))d^{e(G)}(1 − d)^{\binom{s}{k}−e(G)}n^{s} × \binom{t}{s} + O_{1} (\frac{1}{t}\binom{s}{2}\binom{m}{s})

= (1 + O_{1}(2ε))\binom{m}{s}d^{e(G)}(1 − d)^{\binom{s}{k}−e(G)}. (14)

Owing to (12b), we have

\frac{1}{t}\binom{s}{2}\binom{m}{s} < \frac{ε}{100}\binom{m}{s}d^{e(G)}(1 − d)^{\binom{s}{k}−e(G)},  (15a)

and

t^{s} − \binom{s}{2}t^{s−1} > t^{s} − \frac{ε}{100}t^{s}.  (15b)

Since (15a) holds, (14) follows from the following inequality

(1 − ε/2)\binom{m}{s} ≤ n^{s}\binom{t}{s} ≤ (1 + ε/2)\binom{m}{s}.

While the right-hand side of this inequality is immediate, the left-hand side is a consequence of (15b). □

3.4. Proof of P′_{5} ⇒ P′_{6} ⇒ P_{6} and P′_{5} ⇒ P_{5} ⇒ P_{6}. Implications P_{5} ⇒ P_{6} and P′_{5} ⇒ P′_{6} are trivial since P_{6} (respectively, P′_{6}) is a special case of P_{5} (respectively, P′_{5}). Moreover, P′_{6} ⇒ P_{6} is a special case of P′_{5} ⇒ P_{5}, therefore, it suffices to prove that P′_{5} ⇒ P_{5}.

Proof of P′_{5} ⇒ P_{5}. Given two hypergraphs G and H, let us denote by \binom{H}{G}_{inj} the set of injections φ: V (G) → V (H) such that φ(g) ∈ H if and only if g ∈ G. Moreover, we write \binom{H}{G}_{inj}^{w} for the set of such injections such that φ(g) ∈ H when-

ever g ∈ G. Thus, \binom{H}{G}_{inj} is the set of embeddings φ of G into H such that φ(V (G))

induces an isomorphic copy of G in H, whereas \binom{H}{G}_{inj}^{w} is the set of embeddings φ such that φ(V (G)) induces a superhypergraph of G in H. If G has automorphism group Aut(G), it is easy to verify that we have

|\binom{H}{G}_{inj}| = |\binom{H}{G}| | Aut(G)|,  (16)

and similarly for \binom{H}{G}_{inj}^{w} and \binom{H}{G}^{w}.

Suppose now that H is an ordered hypergraph with ordering ≺′. Then,

\binom{H}{G}_{inj} = ⋃_{≺} \binom{H_{≺′}}{G_{≺}},  (17)

where the union ranges over the set of all total orderings ≺ of V (G). Furthermore, a moment’s thought shows that the union in (17) is a disjoint union. Hence

|\binom{H}{G}_{inj}| = ∑_{≺} |\binom{H_{≺′}}{G_{≺}}| .  (18)

Since P′_{5} holds, we have

|\binom{H_{≺′}}{G_{≺}}| = (1 + o(1))\binom{m}{s}d^{e(G)}(1 − d)^{\binom{s}{k}−e(G)}

for every total ordering ≺ of V (G). Since there exist s! total orderings of V (G), combining (16) and (18) yields P_{5}. □

3.5. Minimization of octahedra from subhypergraph counting. We now prove that property P_{6} (which concerns a certain ‘subhypergraph counting formula’ for induced subhypergraphs) implies property P_{4} (which concerns the number of (weak) subhypergraphs isomorphic to octahedra). The proof will have two parts. In the first part we shall show that, for every hypergraph H with density d, the number of copies of K_{k}(2) in H is bounded from below by

(1 + o(1))\frac{m^{2k}}{2^{k}k!}d^{2^{k}}

(see Lemma 3.5). In the second part, we shall prove that P_{6} implies the asymptotic equality (3) given in property P_{4} of Theorem 1.3. We start with the following lemma.

Lemma 3.4. Suppose the k-uniform hypergraph H with m vertices and with density d = d(H) is such that H_{P} satisfies

|\binom{H_{P}}{K_{k}(2)}^{w}| ≳ \frac{n^{2k}}{2^{k}} d^{2^{k}}  (19)

for almost all partitions P = (V_{i})_{1}^{k} of the vertex set V = V (H), where n = m/k. Then

|\binom{H}{K_{k}(2)}^{w}| ≳ \frac{m^{2k}}{2^{k}k!}d^{2^{k}}.  (20)

Proof. This lemma follows easily from a double counting argument. Let us consider the family of pairs (K, P) such that

(i) K_{k}(2) ≅ K ⊂ H, (ii) P = (V_{i})_{1}^{k} is such that (19) holds and |V_{i}| ∼ n = m/k (1 ≤ i ≤ k),

and, finally,

(iii) K ⊂ H_{P}. On the one hand, the number N of such pairs (K, P) is

∑_{P} |{K: (i) and (iii) hold}|,  (21)

where the sum is over all P for which (ii) holds. Thus, because of our assumption on H and Fact 2.10, we have that

N ≳ k^{m} \frac{n^{2k}}{2^{k}} d^{2^{k}}.  (22)

On the other hand, we have that

N = ∑_{K} |\{P: (ii) and (iii) hold\}| ∼ |\binom{H}{K_{k}(2)}^{w}| k!k^{m−2k},  (23)

where the sum is over all K that satisfy (i). Above, we again made use of Fact 2.10 to estimate the number of relevant partitions P for each fixed K. Comparing (22) and (23), we deduce (20). □

The proof of the lower bound on the number of K_{k}(2) in H is straightforward now.

Lemma 3.5. For any m-vertex k-uniform hypergraph H with density d = d(H),

|\binom{H}{K_{k}(2)}^{w}| ≳ \frac{m^{2k}}{2^{k}k!}d^{2^{k}}.  (24)

Proof. We know that all but o(1)k^{m} partitions P satisfies |V_{i}| = n ∼ m/k and d(H_{P}) ∼ d (see Fact 2.10). By Claim 5.2 we know that

|\binom{H_{P}}{K_{k}(2)}| ≳ \frac{n^{2k}}{2^{k}} d^{2^{k}},

and, therefore, by Lemma 3.4, (24) holds. □

Proof of P_{6} ⇒ P_{4}. Let H be a k-uniform hypergraph on m vertices such that, for any k-uniform hypergraph G on 2k vertices, we have

|\binom{H}{G}| ∼ \binom{m}{2k}d^{e(G)}(1 − d)^{\binom{2k}{k}−e(G)} \frac{(2k)!}{| Aut(G)|},  (25)

where d = d(H) is the density of H and Aut(G) is the automorphism group of G. From (16) it follows that, for any such G, we have

|\binom{H}{G}_{inj}| ∼ (m)_{2k}d^{e(G)}(1 − d)^{\binom{2k}{k}−e(G)},  (26)

where, as usual, (a)_{b} = a(a − 1) … (a − b + 1). We are interested in estimating |\binom{H}{G}_{inj}^{w}|. Clearly,

\binom{H}{G}_{inj}^{w} = ⋃_{G′} \binom{H}{G′}_{inj},  (27)

where the union ranges over all k-uniform hypergraphs G′ with the same vertex set as G and G′ ⊃ G. Furthermore, a moment’s thought shows that the union in (27) is a disjoint union. Hence

|\binom{H}{G}_{inj}^{w}| = ∑_{G′} |\binom{H}{G′}_{inj}|

∼ ∑_{G′}(m)_{2k}d^{e(G′)}(1 − d)^{\binom{2k}{k}−e(G′)}

= ∑_{t≥0} ∑_{e(G′)=e(G)+t}(m)_{2k}d^{e(G)+t}(1 − d)^{\binom{2k}{k}−e(G)−t}

= ∑_{t≥0} \binom{\binom{2k}{k} − e(G)}{t}(m)_{2k}d^{e(G)+t}(1 − d)^{\binom{2k}{k}−e(G)−t}

= (m)_{2k}d^{e(G)} ∑_{t≥0} \binom{\binom{2k}{k} − e(G)}{t}d^{t}(1 − d)^{\binom{2k}{k}−e(G)−t}

= (m)_{2k}d^{e(G)}.

Thus,

|\binom{H}{K_{k}(2)}_{inj}^{w}| ∼ (m)_{2k}d^{2^{k}}.

It now suffices to recall the analogue of (16) for weak subhypergraphs to conclude the proof of P_{4}, since | Aut(K_{k}(2))| = k!2^{k}. □

4. Proof of C_{1} ⇔ C_{2}

In this section, we shall prove the equivalence of conditions C_{1} and C_{2} in Theorem 2.13. We start with a fairly standard proof of C_{1} ⇒ C_{2} (see Section 4.1), and then, in Section 4.2, we prove the converse C_{2} ⇒ C_{1}.

4.1. Proof of C_{1} ⇒ C_{2}. The proof follows from the two claims below.

Claim 4.1. Suppose 0 < ε^{1/2} < d, V = V_{1} ∪ ⋯ ∪ V_{k}, |V_{1}| = ⋯ = |V_{k}| = n, and let H = (V, E) be a (ε, d)-regular (k, k)-cylinder. Then for all but at most 2ε^{1/2}n vertices x ∈ V_{k}, the link H(x) is (ε^{1/2}, d)-regular.

Proof. Let X^{−} be the set of all vertices x ∈ V_{k} with the following property: there exists a (k − 1, k − 2)-cylinder F_{x} with (k − 1)-partition V_{1} ∪ ⋯ ∪ V_{k−1} such that

|K_{k−1}(F_{x})| ≥ ε^{1/2}n^{k−1},  (28)

but

|H(x) ∩ K_{k−1}(F_{x})| < (d − ε^{1/2}) |K_{k−1}(F_{x})|.  (29)

We also define X^{+} to be the set of all vertices x ∈ V_{k} satisfying (28) for which we have

|H(x) ∩ K_{k−1}(F_{x})| ≥ (d + ε^{1/2}) |K_{k−1}(F_{x})|.

Suppose that |X^{−}| > ε^{1/2}n and define a (k, k − 1)-cylinder G by

G = K_{k−1}^{(k−1)}(V_{1}, …, V_{k−1}) ∪ ⋃_{x∈X^{−}}{e ∪ {x}: e ∈ F_{x}}

Observe that

|K_{k}(G)| = ∑_{x∈X^{−}} |K_{k−1}(F_{x})| ≥ |X^{−}|ε^{1/2}n^{k−1} ≥ εn^{k},

and, therefore, by the regularity of H,

|H ∩ K_{k}(G)| ≥ (d − ε)|K_{k}(G)| = (d − ε) ∑_{x∈X^{−}} |K_{k−1}(F_{x})|.

On the other hand, from (29) we obtain

|H ∩ K_{k}(G)| = ∑_{x∈X^{−}} |H(x) ∩ K_{k−1}(F_{x})| < (d − ε^{1/2}) ∑_{x∈X^{−}} |K_{k−1}(F_{x})|,

which is a contradiction.

Hence |X^{−}| ≤ ε^{1/2}n. Similarly we obtain |X^{+}| ≤ ε^{1/2}n. □

Claim 4.2. Suppose 0 < ε < 1/16, 2ε^{1/2} < d, V = V_{1} ∪ ⋯ ∪ V_{k}, |V_{1}| = ⋯ = |V_{k}| = n, and let H = (V, E) be a (ε, d)-regular (k, k)-cylinder. Then, H(x, y) is (ε^{1/4}, d^{2})-regular for all but at most 4ε^{1/4}n^{2} pairs of vertices x, y ∈ V_{k}.

Proof. From the previous claim we know that there are at most 2ε^{1/2}n vertices x in V_{k} with (ε^{1/2}, d)-irregular link H(x). These vertices form at most 2ε^{1/2}n^{2} pairs and we shall exclude them from further considerations.

For a vertex x ∈ V_{k} denote by Y_{x}^{−} the set of all vertices y ∈ V_{k} with the following property: there exists a (k−1, k−2)-cylinder F_{y} with (k−1)-partition V_{1}∪⋯∪V_{k−1} such that

|K_{k−1}(F_{y})| ≥ ε^{1/4}n^{k−1},  (30)

but

|H(x, y) ∩ K_{k−1}(F_{y})| < (d^{2} − ε^{1/4}) |K_{k−1}(F_{y})|.  (31)

We also denote by Y_{x}^{+} the set of all vertices y ∈ V_{k} for which there is a (k−1, k−2)- cylinder F_{y} that satisfies (30), but

|H(x, y) ∩ K_{k−1}(F_{y})| > (d^{2} + ε^{1/4}) |K_{k−1}(F_{y})|.

Suppose there exists a vertex x ∈ V_{k} with (ε^{1/2}, d)-regular link H(x) for which |Y_{x}^{−}| ≥ ε^{1/4}n. Define a (k, k − 1)-cylinder G by

G = H(x) ∪ ⋃_{y∈Y_{x}^{−}}{e ∪ {y}: e ∈ F_{y}}.

Then

|K_{k}(G)| = ∑_{y∈Y_{x}^{−}} |H(x) ∩ K_{k−1}(F_{y})|.

Note that (30) together with the (ε^{1/2}, d)-regularity of H(x) implies that

|H(x) ∩ K_{k−1}(F_{y})| ≥ (d − ε^{1/2}) |K_{k−1}(F_{y})|

for all y ∈ Y_{x}^{−}. Hence

|K_{k}(G)| ≥ ∑_{y∈Y_{x}^{−}} (d − ε^{1/2}) |K_{k−1}(F_{y})|

≥ (d − ε^{1/2}) |Y_{x}^{−}|ε^{1/4}n^{k−1} ≥ (d − ε^{1/2}) ε^{1/2}n^{k} ≥ εn^{k}. (32)

By the (ε, d)-regularity of H and (32), we have

|H ∩ K_{k}(G)| ≥ (d − ε)|K_{k}(G)| ≥ (d − ε) (d − ε^{1/2}) ∑_{y∈Y_{x}^{−}} |K_{k−1}(F_{y})|.  (33)

On the other hand, the size of H ∩ K_{k}(G) can be bounded from above using (31) as follows:

|H ∩ K_{k}(G)| = ∑_{y∈Y_{x}^{−}} |H(x, y) ∩ K_{k−1}(F_{y})| < (d^{2} − ε^{1/4}) ∑_{y∈Y_{x}^{−}} |K_{k−1}(F_{y})|. (34)

Comparing (33) and (34), we get

(d − ε) (d − ε^{1/2}) < d^{2} − ε^{1/4},

which implies

ε^{1/4} < (ε + ε^{1/2}) d < ε + ε^{1/2},

which is not true for ε < 1/16.

Hence we have |Y_{x}^{−}| ≤ ε^{1/4}n. We also obtain |Y_{x}^{+}| ≤ ε^{1/4}n in exactly the same way. Consequently, the number of “bad” pairs is bounded by 2ε^{1/2}n^{2}+2ε^{1/4}n×n ≤ 4ε^{1/4}n^{2}. □

4.2. Proof of C_{2} ⇒ C_{1}. The objective of this section is to prove the following theorem.

Theorem 4.3. For every δ > 0 and d > 0 there exist ε > 0 and n_{0} ∈ ℕ such that the following holds. If H is a (k + 1, k + 1)-cylinder with (k + 1)-partition V_{1} ∪ ⋯ ∪ V_{k+1} such that

(i) |V_{i}| = n ≥ n_{0} for all i ∈ [k + 1], (ii) |H| = dn^{k+1}, (iii) H(x) is (ε, d)-regular for all but at most εn vertices x ∈ V_{k+1}, and (iv) H(x, y) is (ε, d^{2})-regular for all but at most εn^{2} pairs x, y ∈ V_{k+1},

then H is (δ, d)-regular.

Remark. Here, we work with (k + 1, k + 1)-cylinders to simplify the notation. With this choice, we shall encounter (k + 1)-, k-, and (k − 1)-uniform hypergraphs.

Proof. Let H be a (k + 1, k + 1)-cylinder satisfying assumptions (i)–(iv). We shall assume that

ε = (δ/4)^{32} < δ < d ≤ 1.  (35)

Suppose that H is not (δ, d)-regular, i.e., Definition 2.5 fails. Without loss of generality (by taking complements) we may assume that the second inequality in (6) is not true, therefore, there exists a (k +1, k)-cylinder G = ⋃_{i=1}^{k+1} G_{i} with (k +1)- partition V_{1} ∪ ⋯ ∪ V_{k+1} such that

|K_{k+1}(G)| ≥ δn^{k+1}  (36)

but

\frac{|H ∩ K_{k+1}(G)|}{|K_{k+1}(G)|} > d + δ.  (37)

We now work on this ‘witness’ G for the irregularity of H.

Fact 4.4. There exist subcylinders G′_{i} ⊂ G_{i} (i ∈ [k]) such that G^{∗} = G′_{1} ∪ ⋯ ∪ G′_{k} ∪ G_{k+1} satisfies the following four conditions:

(1) K_{k}(G^{∗}(x)) = ∅ or |K_{k}(G^{∗}(x))| ≥ εn^{k} for all x ∈ V_{k+1},

(2) H(x) is (ε, d)-regular for all x ∈ V_{k+1} with |K_{k}(G^{∗}(x))| ≥ εn^{k},
(3) |K_{k+1}(G^{∗})| ≥ (δ/2)n^{k+1},
(4) |H ∩ K_{k+1}(G^{∗})| ≥ (d + δ/2)|K_{k+1}(G^{∗})|.

Proof. For every vertex x ∈ V_{k+1} with |K_{k}(G(x))| < εn^{k} or with (ε, d)-irregular link H(x), delete all edges in G that contain x. Notice that this operation does not remove any edge from G_{k+1} and produces a subhypergraph G^{∗} = G′_{1} ∪⋯∪G′_{k} ∪G_{k+1} that satisfies conditions (1) and (2).

Moreover, every removal reduces the size of K_{k+1}(G) (and H ∩ K_{k+1}(G)) by at most εn^{k} if |K_{k}(G(x))| < εn^{k} or by at most n^{k} if H(x) is (ε, d)-irregular. Since there are at most εn vertices x with (ε, d)-irregular link, we obtain that

|K_{k+1}(G^{∗})| ≥ |K_{k+1}(G)| − n × εn^{k} − εn × n^{k},

and

|H ∩ K_{k+1}(G^{∗})| ≥ |H ∩ K_{k+1}(G)| − n × εn^{k} − εn × n^{k},

The first inequality together with assumption (36) shows that

|K_{k+1}(G^{∗})| ≥ |K_{k+1}(G)| − 2εn^{k+1} ≥ δn^{k+1} − 2(δ/4)^{32}n^{k+1} ≥ (δ/2)n^{k+1}.

Similarly, the second inequality, (36), and (37) yield

|H ∩ K_{k+1}(G^{∗})| ≥ |H ∩ K_{k+1}(G)| − 2εn^{k+1} ≥ (d + δ)|K_{k+1}(G)| − 2(δ/4)^{32}n^{k+1}
≥ (d + δ/2)|K_{k+1}(G)| + (δ/2)δn^{k+1} − 2(δ/4)^{32}n^{k+1}
≥ (d + δ/2)|K_{k+1}(G^{∗})|,

and the proof is complete. □

We have to work on G^{∗} further to obtain a witness with more structure. We shall need the following definition.

Definition 4.5. For each e ∈ G_{k+1} define two parameters g(e) and h(e) by

g(e) = |{x ∈ V_{k+1} : {x} ∪ e ∈ K_{k+1}(G^{∗})}|,
h(e) = |{x ∈ V_{k+1} : {x} ∪ e ∈ H ∩ K_{k+1}(G^{∗})}|.

Fact 4.6. Put δ′ = δ^{2}/16. Then there exists a subcylinder G′_{k+1} ⊂ G_{k+1} such that G′ = G′_{1} ∪ ⋯ ∪ G′_{k} ∪ G′_{k+1}, where the G′_{i} (i ∈ [k]) are taken from Fact 4.4, satisfies the following five conditions:

(1) K_{k}(G′(x)) = ∅ or |K_{k}(G′(x))| ≥ εn^{k} for all x ∈ V_{k+1},

(2) H(x) is (ε, d)-regular for all x ∈ V_{k+1} with |K_{k}(G′(x))| ≥ εn^{k},
(3) |K_{k+1}(G′)| ≥ δ′n^{k+1},

(4) h(e)/g(e) ≥ d + δ/4 for all e ∈ G′_{k+1},
(5) g(e) ≥ δ′n for all e ∈ G′_{k+1}.

Proof. We decompose G_{k+1} into two subcylinders G_{k+1}^{∗} ∪ G_{k+1}^{∗∗}, where

G_{k+1}^{∗∗} = \{e ∈ G_{k+1} : \frac{h(e)}{g(e)} ≥ d + \frac{δ}{4}\}

and

G_{k+1}^{∗} = G_{k+1}\G_{k+1}^{∗∗}.

Let G^{∗} be as in Fact 4.4. Observe that

∑_{e∈G_{k+1}} g(e) = |K_{k+1}(G^{∗})| ≥^{Fact 4.4 (3)} (δ/2)n^{k+1}

and

∑_{e∈G_{k+1}} h(e) = |H ∩ K_{k+1}(G^{∗})| ≥^{Fact 4.4 (4)} (d + δ/2)|K_{k+1}(G^{∗})|.

Then for G^{∗∗} = G′_{1} ∪ ⋯ ∪ G′_{k} ∪ G_{k+1}^{∗∗} we have

|K_{k+1}(G^{∗∗})| = ∑_{e∈G_{k+1}^{∗∗}} g(e) ≥ ∑_{e∈G_{k+1}^{∗∗}} h(e) = ∑_{e∈G_{k+1}} h(e) − ∑_{e∈G_{k+1}^{∗}} h(e)

> (d + \frac{δ}{2}) |K_{k+1}(G^{∗})| − (d + \frac{δ}{4}) ∑_{e∈G_{k+1}} g(e)

= (d + \frac{δ}{2}) |K_{k+1}(G^{∗})| − (d + \frac{δ}{4}) |K_{k+1}(G^{∗})| = \frac{δ}{4}|K_{k+1}(G^{∗})| ≥ \frac{δ^{2}}{8} n^{k+1}.

Note that at least (δ^{2}/16)n^{k} edges e of G_{k+1}^{∗∗} must have g(e) ≥ (δ^{2}/16)n, otherwise we would have

|K_{k+1}(G^{∗})| < \frac{δ^{2}}{16}n^{k} · n + n^{k} · \frac{δ^{2}}{16}n = \frac{δ^{2}}{8} n^{k+1},

which would be a contradiction. Remove all edges e with g(e) < (δ^{2}/16)n from G_{k+1}^{∗∗} and obtain G′_{k+1}. Then, G′_{k+1} satisfies condition (4) because of the definition of G_{k+1}^{∗∗} ⊃ G′_{k+1}. It satisfies condition (5) because all edges e with g(e) < (δ^{2}/16)n have been removed, and G′ also satisfies condition (3) because

|K_{k+1}(G′)| ≥ |K_{k+1}(G^{∗∗})| − n^{k} · \frac{δ^{2}}{16}n ≥ \frac{δ^{2}}{8} n^{k+1} − \frac{δ^{2}}{16}n^{k+1} = \frac{δ^{2}}{16}n^{k+1}.

Finally, G′ must satisfy (1) and (2) because we did not change any of G′_{i} (i ∈ [k]). □

Before we come back to the proof of Theorem 4.3, we state an auxiliary lemma. Let 0 < α ≤ 1 and 0 < μ < 1 be given. Let G be a bipartite graph with vertex classes X_{1} ∪ X_{2} and let H be a subgraph of G. We call an ordered pair of vertices (x, y) ∈ X_{1} × X_{1} good if

|H(x) ∩ G(y)| = α(1 + O_{1}(μ))|G(x, y)|  (38)

and

|H(x, y)| = α^{2}(1 + O_{1}(μ))|G(x, y)|.  (39)

We also call a pair bad if it is not good.

The auxiliary lemma is as follows.

Lemma 4.7 (Dementieva, Haxell, Nagle, and Rödl [8]). Let 0 < α ≤ 1 and 0 < μ < 1 be given. Suppose the bipartite graphs G and H are such that

∑_{bad (x,y)∈X_{1}×X_{1}} |G(x, y)| < \frac{μα^{2}}{(1 − α)^{2} + α^{2}} ∑_{z∈X_{2}} |G(z)|^{2}.  (40)

Then

∑_{z∈X_{2}}(|H(z)| − α|G(z)|)^{2} ≤ 5μα^{2} ∑_{z∈X_{2}} |G(z)|^{2}.  (41)

The following corollary of the above lemma holds.

Corollary 4.8. Let 0 < α ≤ 1, 0 < μ ≤ 1, and ν > 0 be given. Let G and H be bipartite graphs as in Lemma 4.7. Denote by W the set of all vertices z ∈ X_{2} such that |H(z)| ≥ (α + ν)|G(z)|. Then

∑_{z∈W} |G(z)| ≤ (5μ/ν^{2})^{1/2} |X_{1}||X_{2}|.  (42)

Proof. Clearly, 5μα^{2} ∑_{z∈X_{2}} |G(z)|^{2} ≤ 5μα^{2}|X_{1}|^{2}|X_{2}| ≤ 5μ|X_{1}|^{2}|X_{2}|. On the other hand,

\begin{aligned}∑_{z∈X_{2}}(|H(z)| − α|G(z)|)^{2} & ≥ ∑_{z∈W}(|H(z)| − α|G(z)|)^{2} ≥ ν^{2} ∑_{z∈W} |G(z)|^{2} \\ & ≥ \frac{ν^{2}}{|W |} ( ∑_{z∈W} |G(z)|)^{2} ≥ \frac{ν^{2}}{|X_{2}|} ( ∑_{z∈W} |G(z)|)^{2} . \end{aligned}

Finally, using inequality (41), we get (42). □

We now turn back to the proof of Theorem 4.3. We define two auxiliary bipartite graphs G = (X_{1} ∪ X_{2}, E(G)) and H = (X_{1} ∪ X_{2}, E(H)) in the following way:

\begin{aligned}X_{1} & = V_{k+1}, \\ X_{2} & = V_{1} × ⋯ × X_{k}, \\ E(G) & = \{(x, e): e ∈ K_{k}(G′(x))\}, \\ E(H) & = \{(x, e): e ∈ H(x) ∩ K_{k}(G′(x))\}. \end{aligned}  (43)

Notice that |X_{1}| = n and |X_{2}| = n^{k}. Then

∑_{x∈X_{1}} |G(x)| = ∑_{e∈X_{2}} |G(e)| ≥ ∑_{e∈G′_{k+1}} |G(e)| = |K_{k+1}(G′)| ≥ δ′n^{k+1} = δ′|X_{1}||X_{2}|.

(44)

Now we prove that the graphs G and H defined by (43) satisfy the assumptions of Corollary 4.8 with α = d, μ = ε^{1/2} and ν = δ/4. Indeed, observe that

• if |K_{k}(G′(x, y))| ≥ εn^{k} and H(x) is (ε, d)-regular, then |H(x)∩K_{k}(G′(x, y))| = (d + O_{1}(ε))|K_{k}(G′(x, y))|, i.e.,

|H(x) ∩ G(y)| = d(1 + O_{1}(ε^{1/2}))|G(x, y)|,

and

• if |K_{k}(G′(x, y))| ≥ εn^{k} and H(x, y) is (ε, d^{2})-regular, then |H(x, y)∩K_{k}(G′(x, y))| = (d^{2} + O_{1}(ε))|K_{k}(G′(x, y))|, i.e.,

|H(x, y)| = d^{2}(1 + O_{1}(ε^{1/2}))|G(x, y)|.

Denote by I_{1} the set of all pairs (x, y) such that |G(x, y)| < ε|X_{2}|, by I_{2} the set of all pairs (x, y) such that H(x, y) is (ε, d^{2})-irregular, and by I_{3} the set of all pairs (x, y) such that H(x) is (ε, d)-irregular.

Both observations above imply that every pair (x, y) ∈ X_{1} × X_{1} such that H(x) is (ε, d)-regular, H(x, y) is (ε, d^{2})-regular, and |G(x, y)| ≥ ε|X_{2}| is good. In other words, the set of bad pairs is a subset of I_{1} ∪ I_{2} ∪ I_{3} and, therefore,

∑_{bad (x,y)} |G(x, y)| ≤ ∑_{(x,y)∈I_{1}} |G(x, y)| + ∑_{(x,y)∈I_{2}} |G(x, y)| + ∑_{(x,y)∈I_{3}} |G(x, y)|.

One can easily see that |I_{1}| ≤ |X_{1}|^{2}, |I_{2}| ≤ ε|X_{1}|^{2}, |I_{3}| ≤ ε|X_{1}| × |X_{1}|, and

• ∑_{(x,y)∈I_{1}} |G(x, y)| ≤ ε|X_{2}| × |I_{1}| ≤ ε|X_{1}|^{2}|X_{2}|,

• ∑_{(x,y)∈I_{2}} |G(x, y)| ≤ |X_{2}| × |I_{2}| ≤ ε|X_{1}|^{2}|X_{2}|,

• ∑_{(x,y)∈I_{3}} |G(x, y)| ≤ |X_{2}| × |I_{3}| ≤ ε|X_{1}|^{2}|X_{2}|.

Consequently, ∑_{bad (x,y)} |G(x, y)| ≤ 3ε|X_{1}|^{2}|X_{2}|.

Suppose that condition (40) of Lemma 4.7 is not satisfied, i.e.,

∑_{bad (x,y)} |G(x, y)| ≥ \frac{d^{2}ε^{1/2}}{(1 − d)^{2} + d^{2}} ∑_{z∈X_{2}} |G(z)|^{2}.

Since ∑_{z∈X_{2}} |G(z)|^{2} ≥ (∑_{z∈X_{2}} |G(z)|)^{2} /|X_{2}|, we get

\frac{d^{2}ε^{1/2}}{(1 − d)^{2} + d^{2}} ( ∑_{z∈X_{2}} |G(z)|)^{2} ≤ 3ε|X_{1}|^{2}|X_{2}|^{2}.

In other words,

∑_{z∈X_{2}} |G(z)| ≤ (\frac{3ε ((1 − d)^{2} + d^{2})}{d^{2}ε^{1/2}})^{1/2} |X_{1}||X_{2}|.

On the other hand, we know (see (44)) that ∑_{z∈X_{2}} |G(z)| ≥ (δ^{2}/16)|X_{1}||X_{2}|, and, therefore, comparing both inequalities yields

\frac{δ^{2}}{16} ≤ (\frac{3ε ((1 − d)^{2} + d^{2})}{d^{2}ε^{1/2}})^{1/2} .

This is a contradiction since 3ε×((1 − d)^{2} + d^{2}) /(d^{2}ε^{1/2}) ≤ ε^{1/2}/d^{2} = (δ/4)^{16}/d^{2} ≤ (δ/4)^{14} < δ^{4}/256. Thus, G and H also satisfy condition (40) of Lemma 4.7.

Set W = G′_{k+1}. Then, because of property (3), clearly |W | ≥ (δ^{2}/16)n^{k+1}/n = (δ^{2}/16)n^{k} = (δ^{2}/16)|X_{2}|, and for every e ∈ W we have |H(e)| ≥ (d + δ/4)|G(e)|. We apply Corollary 4.8 and obtain that

∑_{z∈W} |G(z)| ≤ (\frac{80ε^{1/2}}{δ^{2}} )^{1/2} |X_{1}||X_{2}|.

On the other hand, since |G(e)| ≥ (δ^{2}/16)|X_{1}| for every e ∈ W, we get

∑_{z∈W} |G(z)| ≥ |W | × \frac{δ^{2}}{16}|X_{1}| ≥ \frac{δ^{4}}{256}|X_{1}||X_{2}|.

This is a contradiction because

(\frac{80ε^{1/2}}{δ^{2}} )^{1/2} ≤ 4 (\frac{δ}{4})^{7} < \frac{δ^{4}}{256}.

□

5. Proof of C_{2} ⇔ C_{3} ⇔ C_{4}

Sections 5.1, 5.2, and 5.3 are devoted to the proofs of C_{3} ⇒ C_{4}, C_{4} ⇒ C_{3}, and C_{3} ⇒ C_{2} (note that implication C_{2} ⇒ C_{3} trivially holds). In these sections, we shall be sketchy in places because the arguments are standard or somewhat repetitive.

5.1. Proof of C_{3} ⇒ C_{4}. We start with a standard “cherry counting lemma” for bipartite graphs (a cherry is a path of length 2).

Claim 5.1. Let G = (X ∪ Y, E) be a bipartite graph with |X| = n, |Y | = m, and assume that |E| = dmn. For x, x′ ∈ X, put d_{x,x′} = |G(x, x′)|/m. Then

∑\{d_{x,x′}: x, x′ ∈ X, x ≠ x′\} ≥ \binom{dn}{2}.

Proof. Observe first that

∑_{x∈X} |G(x)| = |E| = ∑_{y∈Y} |G(y)|

and

∑_{x≠x′}^{X} |G(x, x′)| = ∑_{y∈Y} \binom{|G(y)|}{2},

where we write ∑_{x≠x′}^{X} for the sum over all pairs {x, x′} of distinct vertices from X. Then

m ∑_{x≠x′}^{X} d_{x,x′} = ∑_{x≠x′}^{X} |G(x, x′)|

= ∑_{y∈Y} \binom{|G(y)|}{2} ≥ m\binom{m^{−1} ∑_{y∈Y} |G(y)|}{2} = m\binom{dn}{2},

where, naturally, we used the convexity of \binom{x}{2}. □

Claim 5.2. Let H = (V_{1} ∪ ⋯ ∪ V_{k}, E) be a (k, k)-cylinder with |E| = dn^{k}, where |V_{i}| = n for all i ∈ [k]. Then the number of copies of K_{k}(2) in H is bounded from below by (1 + o(1))(n^{2k}/2^{k})d^{2^{k}}.

Proof. We proceed by induction on k. For k = 2, the statement follows from the previous claim and the Cauchy–Schwarz inequality. Indeed, let G = (X ∪ Y, E) be a bipartite graph with |X| = |Y | = n, and assume that |E| = dn^{2}. For x, x′ ∈ X, put d_{x,x′} = |G(x, x′)|/n. Here and below we use the notation ∑_{x≠x′}^{X} introduced in the proof of Claim 5.1. Then the number of copies of K_{2}(2) in G is given by

|\binom{G}{K_{2}(2)}| = ∑_{x≠x′}^{X} \binom{|G(x, x′)|}{2} = ∑_{x≠x′}^{X} \binom{d_{x,x′}n}{2}.

By the Cauchy–Schwarz inequality and Claim 5.1, we have

\begin{aligned}|\binom{G}{K_{2}(2)}| & = ∑_{x≠x′}^{X} \binom{d_{x,x′}n}{2} = (1 + o(1))\binom{n}{2} ∑_{x≠x′}^{X} d_{x,x′}^{2} \\ & ≥ (1 + o(1)) (∑_{x≠x′}^{X} d_{x,x′})^{2} ≥ (1 + o(1))\binom{dn}{2}^{2} \\ & = (1 + o(1))\frac{n^{4}}{4} d^{4}. \end{aligned}  (45)

We now proceed to the induction step. Suppose k ≥ 3, suppose that the claim is true for k − 1, and let H = (V_{1} ∪ ⋯ ∪ V_{k}, E) be a (k, k)-cylinder such that |E| = dn^{k}. Consider an auxiliary bipartite graph with bipartition X = V_{k} and Y = V_{1} × ⋯ × V_{k−1} and edge set

E = {(x, y) ∈ X × Y : y ∈ H(x)}.

Then |X| = n and |Y | = m = n^{k−1}. For x, x′ ∈ X, put d_{x,x′} = |G(x, x′)|/m. Using the induction assumption, H(x, x′) contains ≳ n^{2(k−1)}d_{x,x′}^{2^{k−1}}/2^{k−1} copies of K_{k−1}(2). Furthermore, from the previous claim we know that ∑_{x≠x′}^{X} d_{x,x′} ≥ \binom{dn}{2}. Then

|\binom{H}{K_{k}(2)}| = ∑_{x≠x′}^{X} |\binom{H(x, x′)}{K_{k−1}(2)}|

≥ (1 + o(1)) ∑_{x≠x′}^{X} n^{2(k−1)} \frac{1}{2^{k−1}} d_{x,x′}^{2^{k−1}}

≥ (1 + o(1))\frac{n^{2(k−1)}}{2^{k−1}} \binom{n}{2} (\binom{dn}{2} /\binom{n}{2})^{2^{k−1}}

= (1 + o(1))\frac{n^{2k}}{2^{k}} d^{2^{k}},

as required. □

The proof of C_{3} ⇒ C_{4} is then straightforward.

Proof of C_{3} ⇒ C_{4}. The first part (i.e., the inequality) follows from the previous claim. To obtain the asymptotic equality in the case in which the joint links are almost all (ε, d^{2})-regular, we observe the following.

For k = 2 we use the fact that (ε, d^{2})-regularity of joint links means that d_{x,x′} ∼ d^{2} for almost all pairs of vertices x, x′ ∈ V_{k}. Then we have the asymptotic equality at every step of equation (45), which is exactly what we need to show.

For k > 2, since H(x, x′) is (ε, d^{2})-regular for almost all pairs of vertices x, x′ ∈ V_{k}, by the induction assumption H(x, x′) contains (1 + o(1))n^{2(k−1)}(d^{2})^{2^{k−1}}/2^{k−1} copies of K_{k−1}(2). Hence the number of copies of K_{k}(2) containing x, x′ is

(1 + o(1))n^{2(k−1)} \frac{1}{2^{k−1}} (d^{2})^{2^{k−1}},

and so, summing over all x, x′ ∈ X with x ≠ x′, we have that the number of copies of K_{k}(2) in H is

(1 + o(1))\binom{n}{2}n^{2(k−1)} \frac{1}{2^{k−1}} (d^{2})^{2^{k−1}} = (1 + o(1))\frac{n^{2k}}{2^{k}} d^{2^{k}},

as required. □

5.2. Proof of C_{4} ⇒ C_{3}. The proof of this implication will be based on Claims 5.1 and 5.2 and on a standard application of the Cauchy–Schwarz inequality.

Proof of C_{4} ⇒ C_{3}. For k = 2, this implication follows from the following. Let G = (X ∪Y, E) be a bipartite graph with |X| = |Y | = n, and |E| = dn^{2}, and assume that G contains (1 + o(1))n^{4}d^{4}/4 copies of K_{2}(2), i.e., |\binom{G}{K_{2}(2)}| = (1 + o(1))n^{4}d^{4}/4.

But then we must have equality everywhere in (45), which means that d_{x,x′} ∼ d^{2} for almost all pairs of vertices x, x′ ∈ X. This shows, however, that G(x, x′) is (ε, d^{2})-regular for almost all pairs of vertices x, x′ ∈ X.

Assume now we have k > 2. Let H = (V_{1} ∪ ⋯ ∪ V_{k}, E) be a (k, k)-cylinder with |V_{i}| = n for all i ∈ [k] and |E| = dn^{k}. Suppose that H contains (1 + o(1))n^{2k}d^{2^{k}}/2^{k} copies of K_{k}(2).

Consider an auxiliary bipartite graph with bipartition X = V_{k} and Y = V_{1} × ⋯ × V_{k−1} and edge set

E = {(x, y) ∈ X × Y : y ∈ H(x)}.

Then |X| = n and |Y | = m = n^{k−1}. For x, x′ ∈ X, put d_{x,x′} = |G(x, x′)|/m. From Claim 5.1 we obtain

∑_{x≠x′}^{X} d_{x,x′} ≥ \binom{dn}{2},

and so

∑_{x≠x′}^{X} d_{x,x′}^{2^{k−1}} ≥ \binom{n}{2} (\binom{n}{2}^{−1} ∑_{x≠x′}^{X} d_{x,x′})^{2^{k−1}}

≥ \binom{n}{2} (\binom{dn}{2} /\binom{n}{2})^{2^{k−1}} ≥ (1 + o(1))\frac{n^{2}}{2} d^{2^{k}}. (46)

We apply Claim 5.2 to H(x, x′) and obtain that it contains at least

(1 + o(1))n^{2(k−1)}d_{x,x′}^{2^{k−1}}/2^{k−1}

copies of K_{k−1}(2). Consequently

|\binom{H}{K_{k}(2)}| = ∑_{x≠x′}^{X} |\{copies of K_{k}(2) containing x, x′\}|
≥ (1 + o(1)) ∑_{x≠x′}^{X} \frac{n^{2(k−1)}}{2^{k−1}} d_{x,x′}^{2^{k−1}}  (47)

≥^{(46)} (1 + o(1))\frac{n^{2(k−1)}}{2^{k−1}} \frac{n^{2}}{2} d^{2^{k}}

= (1 + o(1))\frac{n^{2k}}{2^{k}} d^{2^{k}}.

On the other hand, by C_{4} we have that

|\binom{H}{K_{k}(2)}| = (1 + o(1))\frac{n^{2k}}{2^{k}} d^{2^{k}}.  (48)

From (47) and (48) we conclude that d_{x,x′} ∼ d^{2} for almost all pairs x, x′ ∈ X = V_{k}, and therefore that H(x, x′) contains (1 + o(1))n^{2(k−1)}(d^{2})^{2^{k−1}}/2^{k−1} copies of K_{k−1}(2). In view of the induction assumption this means that H(x, x′) is (ε, d^{2})- regular for almost all pairs x, x′ ∈ V_{k}, i.e., C_{3} holds. □

5.3. Proof of C_{3} ⇒ C_{2}. We start with the following claim.

Claim 5.3. Let c > 0 be a fixed constant. Let G = (X ∪ Y, E) be a bipartite graph with |X| = n, |Y | = m, and assume that |G(x, x′)| ∼ c^{2}m for almost all pairs x, x′ ∈ X. Then |G(x)| ∼ cm for almost all vertices x ∈ X.

Proof. Indeed, suppose that |G(x)| ≥ (c+ε)m for all vertices x ∈ X′, where X′ ⊂ X is “big”. Let G′ be the subgraph of G induced on X′ ∪ Y and let |G′(y)| = c_{y}|X′| for all y ∈ Y. Note that |G′(x, x′)| = |G(x, x′)| for all x, x′ ∈ X′. Then we have

∑_{x≠x′}^{X′} |G(x, x′)| ∼ \frac{1}{2}c^{2}m|X′|^{2},

where we write ∑_{x≠x′}^{X′} for the sum over all pairs {x, x′} of distinct vertices from X′. On the other hand,

∑_{x≠x′}^{X′} |G(x, x′)| = ∑_{y∈Y} \binom{|G′(y)|}{2} ∼ ∑_{y∈Y} \frac{1}{2}c_{y}^{2}|X′|^{2}.

Hence ∑_{y∈Y} c_{y}^{2} ∼ c^{2}m which implies, by the Cauchy–Schwarz inequality, that c_{y} ∼ c for almost all y ∈ Y. But then,

cm|X′| ∼ ∑_{y∈Y} c_{y}|X′| = E(G′) = ∑_{x∈X′} |G′(x)| ≥ (c + ε)m|X′|,

which is a contradiction. The same applies to the set of all vertices x ∈ X for which |G(x)| ≤ (c − ε)m. □

Now we give a proof of the implication C_{3} ⇒ C_{2}.

Proof of C_{3} ⇒ C_{2}. We proceed by induction on k. For k = 2, the statement follows from Claim 5.3.

Let k > 2 be given. We shall prove that C_{3} ⇒ C_{2} holds for k. Thus, assume that the link H(x, y) is (ε, d^{2})-regular for almost all x, y ∈ V_{k}. We shall prove that for almost all x ∈ V_{k} the link H(x) is (ε′, d)-regular, where ε′ → 0 as ε → 0.

Consider an auxiliary bipartite graph G = (X ∪ Y, E) with bipartition X = V_{k} and Y = [V_{1}]^{2} × ⋯ × [V_{k−1}]^{2} and edge set

E = {(x, y) ∈ X × Y : y spans a copy of K_{k−1}(2) in H(x)}.

Then |X| = n and |Y | = \binom{n}{2}^{k−1} ∼ n^{2(k−1)}/2^{k−1}. Let x and x′ be such that H(x, x′) is (ε, d^{2})-regular. Since H(x, x′) is a (k − 1, k − 1)-cylinder, we may apply the implication C_{3} ⇒ C_{4} that we have already proved to deduce that H(x, x′) contains ∼ n^{2(k−1)}(d^{2})^{2^{k−1}}/2^{k−1} = n^{2(k−1)}d^{2^{k}}/2^{k−1} copies of K_{k−1}(2). This means that almost all pairs of vertices x, x′ ∈ X have their common neighborhood of size |G(x, x′)| ∼ n^{2(k−1)}d^{2^{k}}/2^{k−1}. Setting m = \binom{n}{2}^{k−1} and c = d^{2^{k−1}}, one may apply Claim 5.3 to infer that

|G(x)| ∼ d^{2^{k−1}} \frac{n^{2(k−1)}}{2^{k−1}}  (49)

for almost all x ∈ X. For each x ∈ X, set d_{x} = |H(x)|/n^{k−1}. Using Claim 5.2, we get that

|G(x)| ≳ d_{x}^{2^{k−1}} \frac{n^{2(k−1)}}{2^{k−1}}

for all x and hence d ≳ d_{x} for almost all x ∈ X. However,

dn^{k} = |H| = ∑_{x∈X} |H(x)| = ∑_{x∈X} d_{x}n^{k−1},

whence dn = ∑_{x∈X} d_{x}. We may conclude that d_{x} ∼ d for almost all x ∈ X.

This, in view of (49), means that H(x) satisfies condition C_{4} for (k−1)-cylinders. Since C_{4} ⇒ C_{3} holds for (k − 1)-cylinders (already proved), C_{3} ⇒ C_{2} holds for (k − 1)-cylinders (induction assumption), and C_{2} ⇒ C_{1} holds for (k − 1)-cylinders (already proved), we conclude that H(x) is (ε′, d)-regular for almost all x ∈ X, as required. □

6. Proof of the subhypergraph counting formula

The heart of the proof of P_{1} ⇒ P′_{5} is in proving a counting lemma, which we now formulate. We shall need several definitions and further notation.

Definition 6.1. Let s and k, s ≥ k ≥ 2, be two integers. An (s, k)-complex H is a system {H^{(i)}}_{i=1}^{k} such that

(a) H^{(1)} is a partition V_{1} ∪ ⋯ ∪ V_{s},

(b) H^{(i)} is an (s, i)-cylinder with s-partition H^{(1)} for every 1 < i ≤ k,

(c) H^{(i)} underlies H^{(i+1)} for every 1 ≤ i < k, i.e., H^{(i+1)} ⊂ K_{i+1}(H^{(i)}).

Now we define the notion of regularity for a (k, k)-cylinder with respect to an underlying (k, k − 1)-cylinder.

Definition 6.2. Let G be a (k, k − 1)-cylinder underlying a (k, k)-cylinder H. We say that H is (ε, d)-regular with respect to G if the following condition is satisfied: whenever G′ ⊂ G is a (k, k − 1)-cylinder such that

|K_{k}(G′)| ≥ ε|K_{k}(G)|,

we have

(d − ε)|K_{k}(G′)| ≤ |H ∩ K_{k}(G′)| ≤ (d + ε)|K_{k}(G′)|.

Note that this definition coincides with Definition 2.5 if k = 2 or if G is the complete (k, k − 1)-cylinder on V_{1} ∪ ⋯ ∪ V_{k}. We extend the above definition to the case of (s, k)-cylinders H.

Definition 6.3. Let G be an (s, k − 1)-cylinder underlying an (s, k)-cylinder H. We say that H is (ε, d)-regular with respect to G if H [⋃_{j∈I} V_{j}] is (ε, d)-regular with

respect to G [⋃_{j∈I} V_{j}] for all I ∈ [s]^{k}.

Now we are ready to introduce the concept of regularity for an (s, k)-complex H.

Definition 6.4. Let d = (d_{2}, …, d_{k}) be a vector of positive real numbers such that 0 < d_{i} ≤ 1 for all i = 2, …, k. We say that the (s, k)-complex H is (δ, d)-regular if H^{(i+1)} is (δ, d_{i+1})-regular with respect to H^{(i)} for every 1 ≤ i < k.

Let H^{(k)} be an (s, k)-cylinder with s-partition V_{1} ∪ ⋯ ∪ V_{s}. We say that a copy of a k-uniform hypergraph G ⊂ H^{(k)} is transversal in H^{(k)} if |V (G) ∩ V_{i}| ≤ 1 for all 1 ≤ i ≤ s. Our key counting result is as follows.

Theorem 6.5. Fix 2 ≤ k ≤ s. For any ε > 0 and any d_{2}, …, d_{k} > 0, there exist δ_{0} > 0 and n_{0} ∈ ℕ for which the following assertion holds. If δ < δ_{0} and H is a (δ, d)-regular (s, k)-complex on V_{1}∪⋯∪V_{s}, where d = (d_{2}, …, d_{k}) and |V_{i}| = n ≥

n_{0} for all i, then the number of transversal K_{s}^{(k)} in H^{(k)} is (1+O_{1}(ε))d\binom{s}{k}_{k} … d\binom{s}{2}_{2}n^{s}.

In the proof of this theorem, we shall need the following notions of “link” and “extended link” for complexes.

Definition 6.6. Let H be an (s, k)-complex on V_{1} ∪ ⋯ ∪ V_{s}, where s ≥ k, and x ∈ V_{s}. We define H(x) = {H^{(i)}(x)}_{i=2}^{k} and, if s > k, we also set H̃(x) = {H̃_{x}^{(i)}}_{i=1}^{k}, where H̃_{x}^{(i)} (i ∈ [k]) is the i-uniform hypergraph defined by

H̃_{x}^{(i)} = \begin{cases}H^{(i+1)}(x) & if 1 ≤ i < k, \\ H^{(k)} ∩ K_{k}(H^{(k)}(x)) & if i = k. \end{cases}  (50)

In (50) above, H^{(i)}(x) is the usual link of the vertex x in the (s, i)-cylinder H^{(i)}, and H^{(k)} ∩ K_{k}(H^{(k)}(x)) denotes the (s − 1, k)-cylinder formed by the edges of H^{(k)} that are cliques in the link H^{(k)}(x). Note that H̃(x) can be viewed as an extension of H(x) in a sense that

H̃(x) = H(x) ∪ {H^{(k)} ∩ K_{k}(H^{(k)}(x))}.

It is easy to see that H(x) is an (s − 1, k − 1)-complex and H̃(x) is an (s − 1, k)- complex. Indeed, since H is an (s, k)-complex, for 1 ≤ i < k, we have H^{(i+1)} ⊂ K_{i+1}(H^{(i)}) (cf. Definition 6.1). Hence, for every vertex x ∈ V_{s}, we have

H^{(i+1)}(x) ⊂ K_{i+1}(H^{(i)}(x)),

and, therefore,

H̃_{x}^{(i+1)} ⊂ K_{i+1}(H̃_{x}^{(i)}).

For i = k, we have

H̃_{x}^{(k)} = H^{(k)} ∩ K_{k}(H^{(k)}(x)) ⊂ K_{k}(H^{(k)}(x)) = K_{k}(H̃_{x}^{(k−1)})

directly from Definition 6.6.

The proof of Theorem 6.5 is based on the following two propositions.

Proposition 6.7. For any 2 ≤ k < s, any δ̃ > 0, and any d_{2}, …, d_{k} > 0, there are constants δ > 0 and n_{0} ∈ ℕ for which the following assertion holds. Let H be a (δ, d)-regular (s, k)-complex on V_{1} ∪ ⋯ ∪ V_{s}, where d = (d_{2}, …, d_{k}) and |V_{i}| = n ≥ n_{0} for all i ∈ [s], and let d̃= (d_{2}d_{3}, …, d_{k−1}d_{k}, d_{k}). Then, for all but at most δ̃n vertices x ∈ V_{s}, the extended link H̃(x) is a (δ̃, d̃)-regular (s−1, k)-complex.

Proposition 6.8. For any k > 2, any δ′ > 0, and any d_{2}, …, d_{k} > 0, there are constants δ > 0 and n_{0} ∈ ℕ for which the following assertion holds. Let H be a (δ, d)-regular (k + 1, k)-complex on V_{1} ∪ ⋯ ∪ V_{k+1}, where d = (d_{2}, …, d_{k}) and |V_{i}| = n ≥ n_{0} for all i ∈ [k + 1], and let d′ = (d_{2}d_{3}, …, d_{k−1}d_{k}). Then, for all but at most δ′n vertices x ∈ V_{k+1}, the link H(x) is a (δ′, d′)-regular (k, k − 1)-complex.

For our induction to work, we shall prove Theorem 6.5 and Propositions 6.7 and 6.8 simultaneously.

Proof of Theorem 6.5 and Propositions 6.7 and 6.8. For given s ≥ k ≥ 2, we denote the statement of Theorem 6.5 by S(s, k) and for s > k ≥ 2, we denote the statement of Proposition 6.7 by L(s, k). We shall prove (i)–(vi) below.

(i) The statement S(2, 2) is true.

(ii) The implication S(k, k − 1) ⇒ S(k, k) holds for every k ≥ 3.

(iii) The implication S(s, k), L(s+1, k) ⇒ S(s+1, k) holds for every s ≥ k ≥ 2. (iv) The statement L(3, 2) is true.

(v) The implication L(k + 1, k) ⇒ L(s, k) holds for every s > k ≥ 2.

(vi) The implication S(k, k − 1), L(k + 1, k − 1) ⇒ L(k + 1, k) holds for every k > 2.

From (i)–(vi), one may easily deduce by induction (see the diagram below) that Theorem 6.5 holds for every s ≥ k ≥ 2 and Proposition 6.7 holds for every s > k ≥ 2.

\underbrace{S(2, 2), L(3, 2)}_{(i, iv)} ⟶^{(iii, v)} S(3, 2), L(4, 2) ⟶^{(iii, v)} S(4, 2), L(5, 2) ⟶^{(iii, v)} …

↓^{(ii, vi)}
S(3, 3), L(4, 3) ⟶^{(iii, v)} S(4, 3), L(5, 3) ⟶^{(iii, v)} …
↓^{(ii, vi)}
S(4, 4), L(5, 4) ⟶^{(iii, v)} …

The purpose of Proposition 6.8 is to simplify the proof of (vi) (this is also the reason why we prove this proposition for (k + 1, k)-complexes only). Indeed, if we denote by L′(k) the statement of Proposition 6.8, we shall prove the following:

(vi′) The implication S(k, k − 1), L(k + 1, k − 1) ⇒ L′(k) holds for every k > 2. (vi′′) The implication S(k, k − 1), L′(k) ⇒ L(k + 1, k) holds for every k > 2.

Clearly (vi′) and (vi′′) imply (vi).

Moreover, from (i)–(vi) one can deduce that L′(k) holds for every k > 2, that is, (i)–(vi) yields the proof of Proposition 6.8 as well.

Now we prove statements (i)–(v), (vi′), and (vi′′).

(i) (Proof of S(2, 2)) Statement S(2, 2) follows directly from the definition of regularity: a (δ, d_{2})-regular (2, 2)-cylinder H^{(2)} contains (d_{2} + O_{1}(δ))n^{2} edges.

(ii) (Proof of S(k, k − 1) ⇒ S(k, k)) Suppose now that S(k, k − 1) is true for some k ≥ 3 and let H be a (δ, d)-regular (k, k)-complex. Observe first that {H^{(i)}}_{i=1}^{k−1} forms a (δ, (d_{2}, …, d_{k−1}))-regular (k, k − 1)-complex; therefore, if δ ≪ ε′, the number of transversal K_{k}^{(k−1)} in H^{(k−1)} is (1 +

O_{1}(ε′))d\binom{k}{k−1}_{k−1} … d\binom{k}{2}_{2}n^{k}. Furthermore, we know that H^{(k)} is (δ, d_{k})-regular with respect to H^{(k−1)}. In particular, this means that

(d_{k} − δ) |K_{k}(H^{(k−1)})| ≤ |H^{(k)} ∩ K_{k}(H^{(k−1)})| ≤ (d_{k} + δ) |K_{k}(H^{(k−1)})| .

Since |H^{(k)} ∩ K_{k}(H^{(k−1)})| counts the number of transversal K_{k}^{(k)} in H^{(k)},

we conclude that this number is (1 + O_{1}(ε))d\binom{k}{k}_{k}d\binom{k}{k−1}_{k−1} … d\binom{k}{2}_{2}n^{k}, if ε′ ≪ ε and δ ≪ min{ε, d_{k}}.

(iii) (Proof of S(s, k), L(s + 1, k) ⇒ S(s + 1, k)) Assume that S(s, k) and L(s+1, k) are true for some s ≥ k ≥ 2 and consider a (δ, d)-regular (s+1, k)- complex H on V_{1} ∪ ⋯ ∪ V_{s+1}, where |V_{i}| = n ≫ n_{0} for all i ∈ [s + 1] and n_{0} is a large positive integer.

From L(s+1, k) we know that H̃(x) is a (δ̃, d̃)-regular (s, k)-cylinder for all but δ̃n vertices x ∈ V_{s+1}, as long as δ ≪ δ̃. From S(s, k) we immediately have that H^{(k)} ∩ K_{k}(H^{(k)}(x)) contains

(1 + O_{1}(ε′))d\binom{s}{k}_{k}(d_{k}d_{k−1})^{\binom{s}{k−1}} … (d_{3}d_{2})^{\binom{s}{2}}(d_{2}n)^{s}

transversal K_{s}^{(k)} for any such ‘good’ x if δ̃ ≪ ε′. Each such transversal K_{s}^{(k)} in H^{(k)} ∩ K_{k}(H^{(k)}(x)) together with x span a transversal K_{s+1}^{(k)} in H^{(k)}. Hence, the total number of transversal K_{s+1}^{(k)} in H^{(k)} is bounded from below by

\begin{aligned}(1 − ε′)(1 − δ̃)nd\binom{s}{k}_{k} & (d_{k}d_{k−1})^{\binom{s}{k−1}} … (d_{3}d_{2})^{\binom{s}{2}}(d_{2}n)^{s} \\ & = (1 − ε′)(1 − δ̃)d_{k}^{\binom{s}{k}+\binom{s}{k−1}} … d_{2}^{\binom{s}{2}+\binom{s}{1}}n^{s+1} \\ & ≤ (1 − ε)d\binom{s+1}{k}_{k} … d\binom{s+1}{2}_{2}n^{s+1}. \end{aligned}  (51)

For the upper bound we get

\begin{aligned}(1 + ε′)nd\binom{s}{k}_{k} & (d_{k}d_{k−1})^{\binom{s}{k−1}} … (d_{3}d_{2})^{\binom{s}{2}}(d_{2}n)^{s} + δ̃n × n^{s} \\ & = (1 + ε′)d_{k}^{\binom{s}{k}+\binom{s}{k−1}} … d_{2}^{\binom{s}{2}+\binom{s}{1}}n^{s+1} + δ̃n^{s+1} \\ & ≤ (1 + ε)d\binom{s+1}{k}_{k} … d\binom{s+1}{2}_{2}n^{s+1}, \end{aligned}  (52)

provided that max{ε′, δ̃} ≪ min{ε, d_{2}, …, d_{k}}. (iv) (Proof of L(3, 2)) Let H^{(2)} be a (δ, d_{2})-regular (3, 2)-cylinder and, for

x ∈ V_{3} and i = 1, 2, set V′_{i} = H_{i}^{(2)}(x). It follows from Claim 4.1 that (d_{2} − δ)n ≤ |V′_{i}| ≤ (d_{2} + δ)n, i = 1, 2, for all but 2δ^{1/2}n vertices x ∈ V_{3}. We shall show that H^{(2)}[V′_{1} ∪ V′_{2}] is (2δ^{1/2}, d_{2})-regular.

Indeed, let U_{1} ⊂ V′_{1}, U_{2} ⊂ V′_{2}, such that |K_{2}(U_{1} ∪ U_{2})| ≥ 2δ^{1/2}|V′_{1}||V′_{2}|. Note that 2δ^{1/2}|V′_{1}||V′_{2}| ≥ 2δ^{1/2}(d_{2} − δ)^{2}n^{2} ≥ δn^{2} = δ|V_{1}||V_{2}|, where we used the fact that δ ≪ d_{2}. The (δ, d_{2})-regularity of H^{(2)} concludes the argument.

(v) (Proof of L(k + 1, k) ⇒ L(s, k)) This fact follows from the simple observation that every (s, k)-complex H can be viewed as a union of \binom{s−1}{k} many (k + 1, k)-complexes that contain V_{s}.

(vi′) (Proof of S(k, k − 1), L(k + 1, k − 1) ⇒ L′(k)) Assume that statements S(k, k − 1) and L(k + 1, k − 1) are true and let H = {H^{(i)}}_{i=1}^{k} be a (δ, d)-regular (k + 1, k)-complex on V_{1} ∪ ⋯ ∪ V_{k+1}, where |V_{i}| = n ≫ n_{0} for all i ∈ [k + 1] and n_{0} is a large positive integer.

To prove L′(k), it suffices to show that for all but at most δ′n vertices x ∈ V_{k+1}, the link H(x) is a (δ′, d′)-regular (k, k − 1)-complex, where d′ = (d_{2}d_{3}, …, d_{k−1}d_{k}) and δ′ → 0 as δ → 0.

Observe first that {H^{(i)}}_{i=1}^{k−1} is a (δ, (d_{2}, d_{3}, …, d_{k−1}))-regular (k +1, k − 1)-complex. Thus, we can apply statement L(k + 1, k − 1) on {H^{(i)}}_{i=1}^{k−1} and obtain that (cf. (50))

(a) {H^{(i)}(x)}_{i=2}^{k−1} is a (δ̃, (d_{2}d_{3}, …, d_{k−2}d_{k−1}))-regular (k, k − 2)-complex, and

(b) H^{(k−1)}∩K_{k−1}(H^{(k−1)}(x)) is (δ̃, d_{k−1})-regular with respect to H^{(k−1)}(x) for all but at most δ̃n vertices x ∈ V_{k+1},where δ̃ → 0 as δ → 0.

Hence, the only thing remaining to prove statement L′(k) is the regularity of H^{(k)}(x) with respect to H^{(k−1)}(x). We do this by showing that for all but 4kδ̃^{1/2}n vertices x ∈ V_{k+1} satisfying (a) and (b), the link H^{(k)}(x) is (2δ̃^{1/2}, d_{k−1}d_{k})-regular with respect to H^{(k−1)}(x). Consequently, H(x) is a (δ′, d′)-regular for all but at most δ′n vertices x ∈ V_{k+1}, where δ′ = δ̃ + 4kδ̃^{1/2} → 0 as δ → 0.

Suppose that there exist t ≥ 2δ̃^{1/2}n vertices x_{1}, …, x_{t} satisfying (a) and (b) for which H^{(k)}(x_{i}) is not (2δ̃^{1/2}, d_{k−1}d_{k})-regular with respect to H^{(k−1)}(x_{i}), i ∈ [t]. More precisely, suppose that for every i ∈ [t], there exists a (k − 1, k − 2)-cylinder G_{i} ⊂ H^{(k−1)}(x_{i}) such that

|K_{k−1}(G_{i})| ≥ 2δ̃^{1/2}|K_{k−1}(H^{(k−1)}(x_{i}))|  (53a)

and

|H^{(k)}(x_{i}) ∩ K_{k−1}(G_{i})| < (d_{k−1}d_{k} − 2δ̃^{1/2})|K_{k−1}(G_{i})|.  (53b)

Suppose further that these (k − 1, k − 2)-cylinders have (k − 1)-partition V_{1} ∪ ⋯ ∪ V_{k−1}. We define a (k, k − 1)-cylinder G by

G = H^{(k−1)}[V_{1} ∪ ⋯ ∪ V_{k−1}] ∪ ⋃_{i=1}^{t} {x_{i} ∪ e: e ∈ G_{i}} .

It is easy to see that

|K_{k}(G)| = ∑_{i=1}^{t} |H^{(k−1)} ∩ K_{k−1}(G_{i})|  (54a)

and

|H^{(k)} ∩ K_{k}(G)| = ∑_{i=1}^{t} |H^{(k)}(x_{i}) ∩ K_{k−1}(G_{i})|.  (54b)

We combine equations (53b) and (54b) and obtain

|H^{(k)} ∩ K_{k}(G)| < (d_{k−1}d_{k} − 2δ̃^{1/2}) ∑_{i=1}^{t} |K_{k−1}(G_{i})|.

On the other hand, we shall show that

|H^{(k)} ∩ K_{k}(G)| ≥ (d_{k−1}d_{k} − 2δ̃^{1/2}) ∑_{i=1}^{t} |K_{k−1}(G_{i})|,  (55)

which will be a contradiction. Thus, t < 2δ̃^{1/2}n. The same applies to the cases in which all the (k − 1, k − 2)-complexes G_{i} have the same (k − 1)- partition V_{1} ∪⋯∪V_{k} \V_{j} for some j ∈ [k], or when we consider the opposite inequality in (53b).

Now we deduce (55). Using assumption (b), (53a), G_{i} ⊂ H^{(k−1)}(x_{i}), and 2δ̃^{1/2} ≥ δ̃, we obtain that for every i ∈ [t],

\begin{aligned}|H^{(k−1)} ∩ K_{k−1}(G_{i})| & ≥ (d_{k−1} − δ̃)|K_{k−1}(G_{i})| \\ & ≥^{(53a)} 2δ̃^{1/2}(d_{k−1} − δ̃)|K_{k−1}(H^{(k−1)}(x_{i}))|. \end{aligned}  (56)

Consequently, combining (54a) and (56) yields

|K_{k}(G)| ≥ 2δ̃^{1/2}(d_{k−1} − δ̃) ∑_{i=1}^{t} |K_{k−1}(H^{(k−1)}(x_{i}))|.  (57)

For k > 3, by (a), the (k, k − 2)-complex {H^{(i)}(x)}_{i=2}^{k−1} restricted on V_{1} ∪ ⋯ ∪ V_{k−1} is a (δ̃, (d_{2}d_{3}, …, d_{k−2}d_{k−1}))-regular (k − 1, k − 2)-complex, and hence by S(k − 1, k − 2) we have

\begin{aligned}|K_{k−1} (H^{(k−1)}(x_{i}))| & = (1 + O_{1}(1/4))(d_{k−1}d_{k−2})^{\binom{k−1}{k−2}} … (d_{3}d_{2})^{\binom{k−1}{2}}(d_{2}n)^{k−1} \\ & = (1 + O_{1}(1/4))d\binom{k−1}{k−2}_{k−1}d\binom{k}{k−2}_{k−2} … d\binom{k}{2}_{2}n^{k−1}, \end{aligned}

provided that δ̃ ≪ min{d_{2}, …, d_{k−1}, 1/4}. It follows from (δ, d_{2})-regularity of H^{(2)} that this equation holds also for k = 3. We may assume that S(k − 1, k − 2) is true since this has already been verified in our inductive proof of S(k, k − 1) (see the proof diagram above). Hence,

|K_{k}(G)| ≥ t × 2δ̃^{1/2}(d_{k−1} − δ̃) × (1 − 1/4)d\binom{k−1}{k−2}_{k−1}d\binom{k}{k−2}_{k−2} … d\binom{k}{2}_{2}n^{k−1} (58)

≥ 2δ̃d\binom{k}{k−1}_{k−1}d\binom{k}{k−2}_{k−2} … d\binom{k}{2}_{2}n^{k}.

Since, {H^{(i)}[V_{1}∪⋯∪V_{k−1}∪V_{k+1}]}_{i=1}^{k−1} is a (δ, (d_{2}, …, d_{k−1}))-regular (k, k− 1)-complex, using S(k, k − 1), we obtain

|K_{k} (H^{(k−1)}[V_{1} ∪ ⋯ ∪ V_{k−1} ∪ V_{k+1}])| = (1 + O_{1}(1/4))d\binom{k}{k−1}_{k−1} … d\binom{k}{2}_{2}n^{k}, (59)

provided that δ ≪ min{d_{2}, …, d_{k−1}, 1/4}.

Combining (58) and (59) yields

|K_{k}(G)| ≥ δ̃|K_{k} (H^{(k−1)}[V_{1} ∪ ⋯ ∪ V_{k−1} ∪ V_{k+1}])| .  (60)

We apply (δ, d_{k})-regularity of H^{(k)} with respect to H^{(k−1)} and obtain

|H^{(k)} ∩ K_{k}(G)| ≥ (d_{k} − δ)|K_{k}(G)|.  (61)

Putting equations (54a), (56), and (61) together yields

|H^{(k)} ∩ K_{k}(G)| ≥ (d_{k} − δ) × (d_{k−1} − δ̃) ∑_{i=1}^{t} |K_{k−1}(G_{i})|

≥ (d_{k}d_{k−1} − 2δ̃^{1/2}) ∑_{i=1}^{t} |K_{k−1}(G_{i})|,

provided that δ ≪ δ̃. (vi′′) (Proof of S(k, k − 1), L′(k) ⇒ L(k + 1, k)) Assume that statements

S(k, k−1) and L′(k) are true and let H be a (δ, d)-regular (k+1, k)-complex on V_{1} ∪ ⋯ ∪ V_{k+1}, where |V_{i}| = n ≫ n_{0} forl all i ∈ [k + 1] and n_{0} is a large positive integer.

To prove L(k +1, k), we need to show that for all but at most δ̃n vertices x ∈ V_{k+1}, the extended link H̃(x) is a (δ̃, d̃)-regular (k, k)-complex, where d̃= (d_{2}d_{3}, …, d_{k−1}d_{k}, d_{k}) and δ̃ → 0 as δ → 0.

Our assumption that L′(k) is true means that {H̃_{x}^{(i)}}_{i=1}^{k−1} = {H^{(i)}(x)}_{i=2}^{k} = H(x) is a (δ′, (d_{2}d_{3}, …, d_{k−1}d_{k}))-regular (k, k − 1)-complex for all but at most δ′n vertices x ∈ V_{k+1}, where δ′ → 0 as δ → 0.

Hence, the only thing remaining to prove L(k + 1, k) is the regularity of H̃_{x}^{(k)} = H^{(k)} ∩ K_{k}(H^{(k)}(x)) with respect to H̃_{x}^{(k−1)} = H^{(k)}(x) for almost all vertices x ∈ V_{k+1}. We prove this by showing that H^{(k)} ∩ K_{k}(H^{(k)}(x)) is (2δ′^{1/2}, d_{k})-regular with respect to H^{(k)}(x) for every x ∈ V_{k+1} for which the link H(x) is (δ′, (d_{2}d_{3}, …, d_{k−1}d_{k}))-regular. Then, H̃(x) is a (δ̃, d̃)-regular for all but at most δ̃n vertices x ∈ V_{k+1}, where δ̃ = 2δ′^{1/2} → 0 as δ → 0.

Suppose that G is a (k, k −1)-cylinder, G ⊂ H^{(k)}(x), such that |K_{k}(G)| ≥ 2δ′^{1/2}|K_{k}(H^{(k)}(x))|. We need to show that

(d_{k}−2δ′^{1/2}) |K_{k}(G)| ≤ |H^{(k)} ∩ K_{k}(H^{(k)}(x)) ∩ K_{k}(G)| ≤ (d_{k}+2δ′^{1/2}) |K_{k}(G)| . (62)

Since G ⊂ H^{(k)}(x) and, therefore, K_{k}(G) ⊂ K_{k}(H^{(k)}(x)), we have

|H^{(k)} ∩ K_{k}(H^{(k)}(x)) ∩ K_{k}(G)| = |H^{(k)} ∩ K_{k}(G)| .  (63)

Consequently, (62) is simply

(d_{k} − 2δ′^{1/2}) |K_{k}(G)| ≤ |H^{(k)} ∩ K_{k}(G)| ≤ (d_{k} + 2δ′^{1/2}) |K_{k}(G)| .  (64)

Observe first that

• since {H^{(i)}(x)}_{i=2}^{k} is a (δ′, (d_{2}d_{3}, …, d_{k−1}d_{k}))-regular (k, k−1)-complex (by our choice of x), by S(k, k − 1) we have

|K_{k} (H^{(k)}(x))| = (1 + O_{1}(1/4))(d_{k}d_{k−1})^{\binom{k}{k−1}} … (d_{3}d_{2})^{\binom{k}{2}}(d_{2}n)^{k},  (65)

provided that δ′ ≪ min{d_{2}, …, d_{k}, 1/4};

• similarly, {H^{(i)}[V_{1} ∪⋯∪V_{k}]}_{i=1}^{k−1} is a (δ, (d_{2}, …, d_{k−1}))-regular (k, k − 1)-complex; thus, using S(k, k − 1) again,

|K_{k} (H^{(k−1)}[V_{1} ∪ ⋯ ∪ V_{k}])| = (1 + O_{1}(1/4))d\binom{k}{k−1}_{k−1} … d\binom{k}{2}_{2}n^{k},  (66)

provided that δ ≪ min{d_{2}, …, d_{k}, 1/4}.

Now we use equations (65) and (66) to derive (64). Indeed, since we as-

sume that δ ≪ δ′ ≪ min\{d_{2}, …, d_{k}\}, we have d\binom{k}{k−1}_{k} … d\binom{k}{2}_{3}d_{2}^{k} ≥ δ^{1/2}.

Consequently,

|K_{k}(G)| ≥ 2δ′^{1/2}|K_{k}(H^{(k)}(x))| ≥^{(65)} 2δ^{1/2}(1 − 1/4)(d_{k}d_{k−1})^{\binom{k}{k−1}} … (d_{3}d_{2})^{\binom{k}{2}}(d_{2}n)^{k}

≥ δ(1 + 1/4)d\binom{k}{k−1}_{k−1} … d\binom{k}{2}_{2}n^{k} ≥^{(66)} δ |K_{k} (H^{(k−1)}[V_{1} ∪ ⋯ ∪ V_{k}])| . (67)

Finally, the (δ, d_{k})-regularity of H^{(k)} with respect to H^{(k−1)} gives (64).

□

In Definition 6.3, we assumed that for every I ∈ [s]^{k}, the restriction H [⋃_{j∈I} V_{j}]

is (ε, d)-regular with respect to G [⋃_{j∈I} V_{j}]. In other words, the density d_{I} of the

subgraph H [⋃_{j∈I} V_{j}] is roughly the same for every I ∈ [s]^{k}. Now we allow different

values of d_{I} (I ∈ [s]^{k}) and state a straightforward extension of Theorem 6.5. We start with some definitions.

Definition 6.9. Let G be an (s, k −1)-cylinder underlying an (s, k)-cylinder H and let d⃗ = (d_{I})_{I∈[s]^{k}} be a list of \binom{s}{k} positive real numbers d_{I}, where 0 < d_{I} ≤ 1. We

say that H is (ε, d⃗)-regular with respect to G if H [⋃_{j∈I} V_{j}] is (ε, d_{I})-regular with

respect to G [⋃_{j∈I} V_{j}] for all I ∈ [s]^{k}.

Definition 6.10. For every integer i (2 ≤ i ≤ k) let d⃗_{i} = (d_{I})_{I∈[s]^{i}} be a list of \binom{s}{i} positive real numbers d_{I}, where 0 < d_{I} ≤ 1, and put d⃗ = (d⃗_{2}, …, d⃗_{k}). We say that the (s, k)-complex H is (δ, d⃗)-regular if H^{(i+1)} is (δ, d⃗_{i+1})-regular with respect to H^{(i)} for every 1 ≤ i < k.

Now we are ready to state an extension of Theorem 6.5.

Corollary 6.11. Fix 2 ≤ k ≤ s. For any ε > 0 and any d⃗_{2}, …, d⃗_{k} as described in Definition 6.10, there exist δ_{0} > 0 and n_{0} ∈ ℕ for which the following assertion holds. If δ < δ_{0} and H is a (δ, d⃗)-regular (s, k)-complex on V_{1} ∪ ⋯ ∪ V_{s}, where |V_{i}| = n ≥ n_{0} for all i, then the number of transversal K_{s}^{(k)} in H^{(k)} is (1 + O_{1}(ε)) ∏_{i=2}^{k} ∏_{I∈[s]^{i}} d_{I} × n^{s}.

The proof of this corollary follows the lines of the proof of Theorem 6.5 and we omit it here. For us, the most interesting case occurs when all underlying cylinders are complete, that is d_{I} = 1 for every I ∈ [s]^{i} and 2 ≤ i < k. In this case, the number of transversal K_{s}^{(k)} in H^{(k)} is (1 + O_{1}(ε)) ∏_{I∈[s]^{k}} d_{I} × n^{s}. We restate this observation in the following corollary.

Corollary 6.12. Fix 2 ≤ k ≤ s. For any ε > 0 and any list d⃗ = (d_{I})_{I∈[s]^{k}} of \binom{s}{k} positive real numbers d_{I}, where 0 < d_{I} ≤ 1, there exist δ_{0} > 0 and n_{0} ∈ ℕ for which the following assertion holds. If δ < δ_{0} and H is a (δ, d⃗)-regular (s, k)-cylinder on V_{1} ∪ ⋯ ∪ V_{s}, where |V_{i}| = n ≥ n_{0} for all i ∈ [s], then the number of transversal K_{s}^{(k)} in H is (1 + O_{1}(ε)) ∏_{I∈[s]^{k}} d_{I} × n^{s}.

Let G be an arbitrary k-uniform hypergraph on s vertices v_{1}, …, v_{s}. We define an (s, k)-cylinder H̃ in the following way. For every I ∈ [s]^{k}, we set

H̃ [⋃_{i∈I} V_{i}] = \begin{cases}H [⋃_{i∈I} V_{i}] & if \{v_{i}: i ∈ I\} ∈ E(G), \\ H̄ = (∏_{i∈I} V_{i}) \ H [⋃_{i∈I} V_{i}] & otherwise. \end{cases}

Observe that every transversal copy of G in H corresponds to exactly one transversal copy of K_{s}^{(k)} in H̃. Consequently, applying the the previous corollary on H̃, we deduce the following counting formula.

Corollary 6.13 (Subhypergraph counting formula). Fix 2 ≤ k ≤ s. For any ε > 0 and any 0 < d ≤ 1, there exist δ_{0} > 0 and n_{0} ∈ ℕ for which the following assertion holds. If the hypergraph H is a (δ, d)-regular (s, k)-cylinder on V_{1} ∪ ⋯ ∪ V_{s}, where |V_{i}| = n ≥ n_{0} for all i ∈ [s] and δ < δ_{0}, and G is an arbitrary k-uniform hypergraph on s vertices, then the number of transversal G in H is (1 + O_{1}(ε))d^{e(G)}(1 − d)^{\binom{s}{k}−e(G)}n^{s}.

Clearly, one may generalize Corollary 6.13 above to the case in which the (s, k)- cylinder H has a non-constant density vector d⃗ = (d_{I})_{I∈[s]^{k}}.

References

[1] N. Alon, R. Duke, H. Lefmann, V. Rödl, and R. Yuster, The algorithmic aspects of the Regularity Lemma, Proceedings of 33rd Annual IEEE FOCS, IEEE 1992, 473–481.

[2] , The algorithmic aspects of the regularity lemma, J. Algorithms 16 (1994), no. 1, 80–109.

[3] L. Babai, N. Nisan, and M. Szegedy, Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs, J. Comput. System Sci. 45 (1992), no. 2, 204–232, Twenty-first Symposium on the Theory of Computing (Seattle, WA, 1989).

[4] F. R. K. Chung, Quasi-random classes of hypergraphs, Random Structures and Algorithms 1 (1990), no. 4, 363–382.

[5] F. R. K. Chung and R. L. Graham, Quasi-random hypergraphs, Random Structures and Algorithms 1 (1990), no. 1, 105–124.

[6] , Quasi-random set systems, Journal of the American Mathematical Society 4 (1991), no. 1, 151–196.

[7] F. R. K. Chung and P. Tetali, Communication complexity and quasi randomness, SIAM J. Discrete Math. 6 (1993), no. 1, 110–123.

[8] Y. Dementieva, P.E. Haxell, B. Nagle, and V. Rödl, On characterizing hypergraph regularity, manuscript, 2001.

[9] J. Haviland and A. G. Thomason, Pseudo-random hypergraphs, Discrete Math. 75 (1989), no. 1–3, 255–278, Graph theory and combinatorics (Cambridge, 1988).

[10] , On testing the “pseudo-randomness” of a hypergraph, Discrete Math. 103 (1992), no. 3, 321–327.

[11] Y. Kohayakawa, V. Rödl, and L. Thoma, An optimal deterministic algorithm for checking regularity, manuscript, 2001.

[12] A. G. Thomason, Pseudorandom graphs, Random graphs ’85 (Poznań, 1985), North-Holland Math. Stud., vol. 144, North-Holland, Amsterdam–New York, 1987, pp. 307–331.

[13] , Random graphs, strongly regular graphs and pseudorandom graphs, Surveys in Combinatorics 1987 (C. Whitehead, ed.), London Mathematical Society Lecture Note Series, vol. 123, Cambridge University Press, Cambridge–New York, 1987, pp. 173–195.

[14] R. M. Wilson, Cyclotomy and difference families in elementary abelian groups, J. Number Theory 4 (1972), 17–47.

Instituto de Matemática e Estatística, Universidade de São Paulo, Rua do Matão 1010, 05508–900 São Paulo, Brazil

E-mail address: yoshi@ime.usp.br

Department of Mathematics and Computer Science, Emory University, Atlanta, GA 30322, USA

E-mail address: rodl@mathcs.emory.edu

Department of Mathematics, University of Illinois at Urbana-Champaign, Urbana, IL, 61820, USA and Department of Mathematics and Computer Science, Emory University, Atlanta, GA 30322, USA

E-mail address: jozef@math.uiuc.edu