Regularity lemma for \(k\)-uniform hypergraphs. (English) Zbl 1046.05042

Summary: Szemerédi’s regularity lemma proved to be a very powerful tool in extremal graph theory with a large number of applications. F. R. K. Chung [Regularity lemmas for hypergraphs and quasi-randomness, Random Struct. Algorithms 2, 241–252 (1991; Zbl 0756.05081)], P. Frankl and V. Rödl [The uniformity lemma for hypergraphs, Graphs Comb. 8, 309–312 (1992; Zbl 0777.05084); Extremal problems on set systems, Random Struct. Algorithms 20, 131–164 (2002; Zbl 0995.05141)] considered several extensions of Szemerédi’s regularity lemma to hypergraphs. In particular, [Extremal problems on set systems, Random Struct. Algorithms 20, 131–164 (2002)] 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.


05C35 Extremal problems in graph theory
05C65 Hypergraphs
Full Text: DOI


[1] Chung, Regularity lemmas for hypergraphs and quasi-randomness, Random Structures Algorithms 2 pp 241– (1991) · Zbl 0756.05081
[2] Czygrinow, An algorithmic regularity lemma for hypergraphs, SIAM J Comput 30 (4) pp 1041– (2000) · Zbl 0971.05084
[3] Frankl, The uniformity lemma for hypergraphs, Graphs Combin 8 (4) pp 309– (1992) · Zbl 0777.05084
[4] Frankl, Extremal problems on set systems, Random Structures Algorithms 20 (2) pp 131– (2002) · Zbl 0995.05141
[5] Frieze, Quick approximation to matrices and applications, Combinatorica 19 (2) pp 175– (1999) · Zbl 0933.68061
[6] W. T. Gowers Hypergraph regularity and the multidimensional Szemerédi theorem 2003
[7] J. Komlós M. Simonovits Szemerédi’s regularity lemma and its applications in graph theory Combinatorics-Paul Erdos is eighty 2 D. Miklós V. T. Sós T. Szonyi 295 352 János Bolyai Mathematical Society Budapest 1996
[8] Komlós, Lecture Notes in Computer Science 2292, in: Theoretical aspects of computer science pp 84– (2002)
[9] Nagle, Regularity properties for triple systems, Random Structures Algorithms 23 (3) pp 264– (2003) · Zbl 1026.05061
[10] B. Nagle V. Rödl M. Schacht The counting lemma for regular k -uniform hypergraphs 2003
[11] Prömel, Excluding induced subgraphs. III. A general asymptotic, Random Structures Algorithms 3 (1) pp 19– (1992) · Zbl 0751.05041
[12] V. Rödl J. Skokan Counting subgraphs in quasi-random 4-uniform hypergraphs
[13] J. Skokan 2000 http://www.mathcs.emory.edu/rodl/grads.html
[14] Szemerédi, On sets of integers containing no k elements in arithmetic progression, Acta Arith 27 pp 199– (1975) · Zbl 0335.10054
[15] E. Szemerédi Regular partitions of graphs 1978 399 401
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.