The counting lemma for regulark‐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: IfGis an ℓ‐partite graph withV(G) =V1∪ … ∪Vℓand ∣︁Vi∣︁ =n for all i∈ [ℓ], and all pairs (Vi,Vj)areε‐regular of density d for1 ≤i≤j≤ ℓandε ≪d,then G contains(1± f_(ε))d²× n^ cliquesKℓ,where fℓ(ε) → 0asε → 0. Recently, Rödl and Skokan generalized Szemerédi's Regularity Lemma from graphs tok‐uniform hypergraphs for arbitraryk≥ 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.