Equivalent Conditions for Regularity (Extended Abstract)

Y. Kohayakawa^{1}^{⋆}, V. Rödl^{2}, and J. Skokan^{2}

1 Instituto de Matemática e Estatística, Universidade de São Paulo,

Rua do Matão 1010, 05508–900 São Paulo, Brazil

                       yoshi@ime.usp.br

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

                {rodl,jozef}@mathcs.emory.edu

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. Chung and Graham proved that having small deviation is equivalent to a variety of other properties that describe quasi-randomness. In this note, 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 give a proof of the fact that having the correct ‘spectrum’ of the s-vertex subhypergraphs is equivalent to quasi-randomness for any s ≥ 2k. Our work can be viewed as an extension of the results of Chung and Graham to the case of an arbitrary constant valued density. Our methods, however, are based on different ideas.

1 Introduction and the main result

The usefulness of random structures in theoretical computer science and in discrete mathematics is well known. An important, closely related question is the following: which, if any, of the almost sure properties of such structures suffice for a deterministic object to have to be as useful or relevant?

Our main concern here is to address the above question in the context of hypergraphs. We shall continue the study of quasi-random hypergraphs along the lines initiated by Haviland and Thomason [7, 8] and especially by Chung [2], and Chung and Graham [3, 4]. One of the central concepts of hypergraph quasirandomness, the so called hypergrpahs discrepancy, was investigated by Babai,

⋆ Partially supported by FAPESP (Proc. 96/04505–2), by CNPq (Proc. 300334/93–1), and by MCT/FINEP (PRONEX project 107/97).

Nisan, and Szegedy [1], who found a connection between communication complexity and hypergraph discrepancy. This connection was further studied by Chung and Tetali [5]. Here, we carry out the investigation very much along the lines of Chung and Graham [3, 4], except that we focus on hypergraphs of arbitrary constant density, making use of different techniques.

In the remainder of this introduction, we carefully discuss a result of Chung and Graham [3] and state our main result, Theorem 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. 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 kelement 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}, let V^{2k} denote the set of all 2k-tuples (v_{1}, v_{2}, …, v_{2k}), where v_{i} ∈ V (1 ≤ i ≤ 2k), and let Π_{H}^{(k)} : V^{2k} → {−1, 1} be given by

Π_{H}^{(k)}(u_{1}, …, u_{k}, v_{1}, …, v_{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.

Following Chung and Graham (see, e.g., [4]), we define the deviation dev(H) of H by

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

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 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), the joint W -link is 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 ordinary graph neighbourhood of x. Moreover, H(x, x′) may be thought of as the ‘joint neighbourhood’ of x and x′.

In [3], 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), we have

|\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 vertices 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 1 ≤ r ≤ 2k − 1 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 to be understood in the following sense. If we have two properties P = P (o(1)) and P′ = P′(o(1)), then “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}(ε).

In [3] Chung and Graham stated that “it would be profitable to explore quasi-randomness 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 [13, 14].” Our present aim is to explore quasirandomness from this point of view. 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. Indeed, it seems to us that the fact that the density of H is 1/2 is essential in certain proofs in [3] (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 later investigated by Chung [2] and Chung and Graham in [3, 4]. 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 by letting 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 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 [2] 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 [2].

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}_{ord} for the number of such embeddings.

As our main result, we shall prove the following extension of Chung and Graham’s result.

Theorem 3 Let H = (V, E) be a k-uniform hypergraph of density 0 < d < 1. Then the following statements are equivalent:

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

for all but o(m^{2}) pairs x, y ∈ V, (P_{3}) disc(H(x, y)) = o(1) for all but o(m^{2}) pairs x, y ∈ V, (P_{4}) the number of octahedra K_{k}(2) in H is asymptotically minimized 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}},

(P_{5}) for any s ≥ 2k and any k-uniform hypergraph 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 any ordering H_{≤} of H and for any fixed integer s ≥ 2k, any ordered k-uniform hypergraph G_{≤} on s vertices with e(G) edges is such that

|\binom{H}{G}_{ord}| = (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 any ordering H_{≤} of H, any ordered k-uniform hypergraph G_{≤} on 2k vertices with e(G) edges is such that

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

Some of the implications in Theorem 3 are fairly easy or are by now quite standard. There are, however, two implications that appear to be more 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 [15]. 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 2.2).

Our second contribution, which is somewhat more technical in nature, lies in a novel approach for the proof of the implication P_{2} ⇒ P_{1}. Our proof is based on a variant of the Regularity Lemma of Szemerédi [12] for hypergraphs [6] (see Section 2.1).

2 Main steps in the proof of Theorem 3

2.1 The first part

The first part of the proof of Theorem 3 consists of proving that properties P_{1}, …, P_{4} are mutually equivalent. As it turns out, the proof becomes more transparent if we restrict ourselves to k-partite hypergraphs. In the next paragraph, we introduce some definitions that will allow us to state the k-partite version of P_{1}, …, P_{4} (see Theorem 15). We close this section introducing the main tool in the proof of Theorem 15, namely, we state a version of the Regularity Lemma for hypergraphs (see Lemma 20).

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

Definition 4 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 5 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.

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

Definition 6 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 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 7 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} ||H ∩ K_{k}(G)| − d(H)|K_{k}(G)||,  (3)

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 8 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}|, then

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

Lemma 9 Let H be an (α, δ)-regular (k, k)-cylinder. Then disc(H) ≤ 2δ.

Lemma 10 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.

The k-partite result. Suppose H is a k-uniform hypergraph and let H′ be a ‘typical’ k-partite spanning subhypergraph of H. In this section, we relate the discrepancies of H and H′.

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

The following lemma holds.

Lemma 12 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}, (ii) disc(H_{P}) ≤ 2 disc(H)m^{k}/|V_{1}| … |V_{k}|.

An immediate consequence of the previous lemma is the following.

Lemma 13 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 Lemma 13.

Lemma 14 Suppose there exists a 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).

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

Theorem 15 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 (d, o(1))-regular; (C_{2}) H(x) is (d, o(1))-regular for all but o(n) vertices x ∈ V_{k} and H(x, y) is

(d^{2}, o(1))-regular for all but o(n^{2}) pairs x, y ∈ V_{k}; (C_{3}) H(x, y) is (d^{2}, o(1))-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 1. The condition |V_{1}| = ⋯ = |V_{k}| = n in the result above has the sole purpose of making the statement more transparent. The immediate generalization of Theorem 15 for V_{1}, …, V_{k} of arbitrary sizes holds.

Remark 2. The fact that the minimal number of octahedra in a (k, k)-cylinder is asymptotically (1 + o(1))n^{2k}d^{2^{k}}/2^{k} is not difficult to deduce from a standard application of the Cauchy–Schwarz inequality for counting “cherries” (paths of length 2) in bipartite graphs.

We leave the derivation of the equivalence of properties P_{1}, …, P_{4} from Theorem 15 to the full paper.

A regularity lemma. The hardest part in the proof of Theorem 15 is the implication C_{2} ⇒ C_{1}. In this paragraph, we discuss the main tool used in the proof of this implication. It turns out that, in what follows, the notation is simplified if we consider (k + 1)-partite hypergraphs.

Throughout this paragraph, we let G be a fixed (k+1, k)-cylinder with vertex set V (G) = V_{1}∪⋯∪V_{k+1}. Recall that G = ⋃_{i=1}^{k+1} G_{i}, where G_{i} is the corresponding (k, k)-cylinder induced on ⋃_{j≠i} V_{j}. In this section, we shall focus on “regularizing” the (k, k)-cylinders G_{1}, …, G_{k}, ignoring G_{k+1}. Alternatively, we may assume that G_{k+1} = ∅.

Definition 16 Let F = ⋃_{i=1}^{k} F_{i} be a (k, k − 1)-cylinder with vertex set V_{1} ∪ ⋯ ∪ V_{k}. For a vertex v ∈ V_{k+1}, we define the G-link G_{F}(x) of x with respect to F to be the (k, k − 1)-cylinder G_{F}(x) = G(x) ∩ F.

Definition 17 Let W ⊂ V_{k+1} and let F = ⋃_{i=1}^{k} F_{i} be as above. We shall say that the pair (F, W) is (ε, d)-regular if

|\frac{|K_{k}(G_{F}(x))|}{|K_{k}(F)|} − d| < ε  (4)

for all but at most ε|W | vertices x ∈ W, and

|\frac{|K_{k}(G_{F}(x)) ∩ K_{k}(G_{F}(y))|}{|K_{k}(F)|} − d^{2}| < ε  (5)

for all but at most ε|W |^{2} pairs x, y ∈ W.

Definition 18 Let t be a positive integer and let V_{k+1} = W_{1} ∪ ⋯ ∪ W_{t} be an arbitrary partition of V_{k+1}. For every i ∈ [k], consider a t-partition P_{i}^{(t)} = {E_{1}^{(i)}, …, E_{t}^{(i)}} of V_{1} × ⋯ × V_{i−1} × V_{i+1} × ⋯ × V_{k} = ⋃_{α=1}^{t} E_{α}^{(i)}. Put P^{(t)} = (P_{1}^{(t)}, …, P_{k}^{(t)}). We shall write E(P^{(t)}) for the collection of all (k, k−1)-cylinders E of the form E_{α_{1}}^{(1)} ∪ ⋯ ∪ E_{α_{k}}^{(k)}, where E_{α_{i}}^{(i)} ∈ P_{i}^{(t)} for all 1 ≤ i ≤ k.

Clearly, with the notation as above, we have |E(P^{(t)})| = t^{k}. Moreover, observe that each of the t^{k+1} pairs (E, W_{i}), where E ∈ E(P^{(t)}) and 1 ≤ i ≤ t, may be classified as ε-regular or ε-irregular (i.e., not ε-regular), according to Definition 17. Also, notice that each v = (v_{1}, …, v_{k+1}) ∈ V_{1} × ⋯ × V_{k+1} is ‘covered’ by exactly one such pair, that is, v ∈ K_{k}(E) × W_{i} for a unique pair (E, W_{i}).

Definition 19 Let P^{(t)} = (P_{i}^{(t)})_{1}^{k} and (W_{i})_{1}^{t} be as in Definition 18. We shall say that the system of partitions {P_{1}^{(t)}, …, P_{k}^{(t)}, {W_{1}, …, W_{t}}} is ε-regular if the number of (k + 1)-tuples (v_{1}, …, v_{k+1}) ∈ V_{1} × ⋯ × V_{k+1} that are not covered by the family of ε-regular pairs (E, W_{i}) with E ∈ E(P^{(t)}) and 1 ≤ i ≤ t is at most ε|V_{1}| … |V_{k+1}|.

The main tool in the proof of C_{2} ⇒ C_{1} is the following result (see [9] for the details).

Lemma 20 For every ε > 0 and t_{0} ≥ 1, there exist integers n_{0} and T_{0} such that every (k + 1, k)-cylinder G = ⋃_{i=1}^{k+1} G_{i} with vertex set V_{1} ∪ ⋯ ∪ V_{k+1}, where |V_{i}| ≥ n_{0} for all 1 ≤ i ≤ k + 1, admits an ε-regular system of partitions {P_{1}^{(t)}, …, P_{k}^{(t)}, {W_{1}, …, W_{t}}} with t_{0} < t < T_{0}.

2.2 The subgraph counting formula

In this section, we shall state the main result that may be used to prove the implication P_{1} ⇒ P′_{5}. To this end, we need to introduce some notation. Throughout this section, s ≥ 2k is some fixed integer.

If H and G are, respectively, k-uniform and ℓ-uniform (k ≥ ℓ), then we say that H is supported on G if H ⊂ K_{k}(G).

Suppose we have pairwise disjoint sets W_{1}, …, W_{s}, with |W_{i}| = n for all i. Suppose further that we have a sequence G^{(2)}, …, G^{(k)} of s-partite cylinders on W_{1} ∪ ⋯ ∪ W_{s}, with G^{(i)} an (s, i)-cylinder and, moreover, such that G^{(i)} is supported on G^{(i−1)} for all 3 ≤ i ≤ k. Suppose also that, for all 2 ≤ i ≤ k and for all 1 ≤ j_{1} < ⋯ < j_{i} ≤ s, the (i, i)-cylinder G[j_{1}, …, j_{i}] = G^{(i)}[W_{j_{1}} ∪ ⋯ ∪ W_{j_{i}}] is (γ_{i}, δ)-regular with respect to G^{(i−1)}[j_{1}, …, j_{i}] = G^{(i−1)}[W_{j_{1}} ∪ ⋯ ∪ W_{j_{i}}], that is, whenever G ⊂ G^{(i−1)}[j_{1}, …, j_{i}] is such that |K_{i}(G)| ≥ δ|K_{i}(G^{(i−1)}[j_{1}, …, j_{i}])|, we have

(γ_{i} − δ)|K_{i}(G)| ≤ |G[j_{1}, …, j_{i}] ∩ K_{i}(G)| ≤ (γ_{i} + δ)|K_{i}(G)|.

Finally, let us say that a copy of K_{s}^{(k)} in W_{1} ∪⋯∪W_{s} is transversal if |V (K_{s}^{(k)})∩ W_{i}| = 1 for all 1 ≤ i ≤ s.

Our main result concerning counting subhypergraphs is then the following.

Theorem 21 For any ε > 0 and any γ_{2}, …, γ_{k} > 0, there is δ_{0} > 0 such that if

δ < δ_{0}, then the number of transversal K_{s}^{(k)} in G^{(k)} is (1 + O(ε))γ\binom{s}{k}_{k} … γ\binom{s}{2}_{2}n^{s}.

Theorem 21 above is an instance of certain counting lemmas developed by Rödl and Skokan for such complexes G = (G^{(i)})_{2≤i≤k} (see, e.g., [11]).

3 Concluding remarks

We hope that the discussion above on our proof approach for Theorem 3 gives some idea about our methods and techniques. Unfortunately, because of space limitations and because we discuss the motivation behind our work in detail, we are unable to give more details. We refer the interested reader to [9].

It is also our hope that the reader will have seen that many interesting questions remain. Probably, the most challenging of them concerns developing an applicable theory of sparse quasi-random hypergraphs. Here, we have in mind such lemmas for sparse quasi-random graphs as the ones in [10].

References

1. 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).

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

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

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

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

6. P. Frankl and V. Rödl, The uniformity lemma for hypergraphs, Graphs and Combinatorics 8 (1992), no. 4, 309–312.

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

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

9. Y. Kohayakawa, V. Rödl, and J. Skokan, Equivalent conditions for regularity, in preparation, 1999.

10. Y. Kohayakawa, V. Rödl, and E. Szemerédi, The size-Ramsey number of graphs of bounded degree, in preparation, 1999.

11. V. Rödl and J. Skokan, Uniformity of set systems, in preparation, 1999.

12. E. Szemerédi, Regular partitions of graphs, Problèmes Combinatoires et Théorie des Graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976) (Paris), Colloques Internationaux CNRS n. 260, 1978, pp. 399–401.

13. 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.

14. , 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.

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