Random Structures and Algorithms · 2004 · 266 citations · 10 references
Natural SciencesComputer ScienceMathematicsAlgorithmsCombinatoricsDiscrete MathematicsExtremal CombinatoricsGraph AlgorithmsGraph TheoryHypergraph TheorySet SystemsHypergraph Extremal ProblemsRandom Graph TheoryUniform Hypergraphs
Abstract 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
10
Quick Approximation to Matrices and Applications
Alan Frieze, Ravi Kannan · COMBINATORICA · 1999 · 518 citations
Extremal problems on set systems
Péter Frankl, Vojtěch Rödl · Random Structures and Algorithms · 2002 · 157 citations