The counting lemma for regular k ‐uniform hypergraphs

Szemerédi's Regularity Lemma proved to be a powerful tool in the area of extremal graph theory. Many of its applications are based on its accompanying Counting Lemma: If G is an ℓ‐partite graph with V ( G ) = V 1 ∪ … ∪ V ℓ and ∣ V i ∣ = n for all i ∈ [ℓ], and all pairs ( V i , V j ) are ε‐ regular of density d for 1 ≤ i ≤ j ≤ ℓ and ε ≪ d , then G contains $(1\pm f_{\ell}(\varepsilon))d^{\ell \choose 2}\times n^{\ell}$ cliques K ℓ , where f ℓ (ε) → 0 as ε → 0. Recently, Rödl and Skokan generalized Szemerédi's Regularity Lemma from graphs to k ‐uniform hypergraphs for arbitrary k ≥ 2. In this paper we prove a Counting Lemma accompanying the Rödl–Skokan hypergraph Regularity Lemma. Similar results were independently obtained by Gowers. Such results give combinatorial proofs to the density result of Szemerédi and some of the density theorems of Furstenberg and Katznelson. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2006