Regularity properties for triple systems

Authors:
Publisher website
Google Scholar
Abstract
Szemerédi's Regularity Lemma proved to be a powerful tool in the area of extremal graph theory J. Komlós and M. Simonovits, Szemerédi's Regularity Lemma and its applications in graph theory, Combinatorics 2 (1996), 295–352. Many of its applications are based on the following technical fact: If G is a k‐partite graph with V(G) = ∪Vi, |Vi| = n for all i ∈ [k], and all pairs {Vi, Vj}, 1 ≤ i < j ≤ k, are ϵ‐regular of density d, then G contains dnk(1 + f(ϵ)) cliques K, where f(ϵ) → 0 as ϵ → 0. The aim of this paper is to establish the analogous statement for 3‐uniform hypergraphs. Our result, to which we refer as The Counting Lemma, together with Theorem 3.5 of P. Frankl and V. Rödl [Extremal problems on set systems, Random Structures Algorithms 20(2) (2002), 131–164, a Regularity Lemma for Hypergraphs, can be applied in various situations as Szemerédi's Regularity Lemma is for graphs. Some of these applications are discussed in previous papers, as well as in upcoming papers, of the authors and others. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 264–332, 2003