Premium
Regularity Lemma for k‐uniform hypergraphs
Author(s) -
Rödl Vojtěch,
Skokan Jozef
Publication year - 2004
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.20017
Subject(s) - lemma (botany) , randomness , mathematics , combinatorics , generalization , discrete mathematics , hypergraph , random graph , set (abstract data type) , graph , computer science , ecology , mathematical analysis , statistics , poaceae , biology , programming language
Szemerédi's Regularity Lemma proved to be a very powerful tool in extremal graph theory with a large number of applications. Chung [Regularity lemmas for hypergraphs and quasi‐randomness, Random Structures Algorithms 2 (1991), 241–252], Frankl and Rödl [The uniformity lemma for hypergraphs, Graphs Combin 8 (1992), 309–312; Extremal problems on set systems, Random Structures Algorithms 20 (2002), 131–164] considered several extensions of Szemerédi's Regularity Lemma to hypergraphs. In particular, [Extremal problems on set systems, Random Structures Algorithms 20 (2002), 131–164] contains a regularity lemma for 3‐uniform hypergraphs that was applied to a number of problems. In this paper, we present a generalization of this regularity lemma to k ‐uniform hypergraphs. Similar results were recently independently and alternatively obtained by W. T. Gowers. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004