Premium
Regularity properties for triple systems
Author(s) -
Nagle Brendan,
Rödl Vojtěch
Publication year - 2003
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.10094
Subject(s) - lemma (botany) , combinatorics , mathematics , extremal graph theory , discrete mathematics , graph , graph theory , statement (logic) , hypergraph , random graph , line graph , voltage graph , ecology , poaceae , political science , law , biology
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 ) = ∪ i =1 kV i , | V i | = n for all i ∈ [ k ], and all pairs { V i , V j }, 1 ≤ i < j ≤ k , are ϵ‐regular of density d , then G contains d ( 2 k )n k (1 + f (ϵ)) cliques K k (2) , 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