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

Rödl, Vojtěch; Skokan, Jozef

Random Struct. Algorithms 25, No. 1, 1-42 (2004).

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.

MSC:

05C35	Extremal problems in graph theory
05C65	Hypergraphs

Keywords:

regularity lemma; uniform hypergraphs; regular partition

Citations:

Zbl 0756.05081; Zbl 0777.05084; Zbl 0995.05141

References:

[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