The counting lemma for regular \(k\)-uniform hypergraphs. (English) Zbl 1093.05045

Nagle, Brendan; Rödl, Vojtěch; Schacht, Mathias

Random Struct. Algorithms 28, No. 2, 113-179 (2006).

Szemerédi’s regularity lemma says roughly that any graph can be partitioned into equal parts so that most subgraphs induced by any two parts have their edges fairly uniformly distributed with a common density. This paper extends this result to \(k\)-uniform hypergraphs and obtains a general counting lemma.

Reviewer: Ove Frank (Stockholm)

MSC:

05C65	Hypergraphs
05C35	Extremal problems in graph theory
05A18	Partitions of sets

Keywords:

regularity lemma; hypergraphs; extremal graph theory

References:

[1]	Bergelson, J Am Math Soc 9 pp 725– (1996)
[2]	Bergelson, Mem Am Math Soc 146 pp viii+106– (2000)
[3]	Chung, Random Struct Algor 2 pp 241– (1991)
[4]	Czygrinow, SIAM J Comput 30 pp 1041– (2000)
[5]	Dementieva, Random Struct Algor 21 pp 293– (2002)
[6]	Erdos, J London Math Soc 11 pp 261– (1936)
[7]	Erdos, Graphs Combin 2 pp 113– (1986)
[8]	Frankl, Graphs Combin 8 pp 309– (1992)
[9]	Frankl, Random Struct Algor 20 pp 131– (2002)
[10]	Frieze, Combinatorica 19 pp 175– (1999)
[11]	Furstenberg, J Anal Math 31 pp 204– (1977)
[12]	Furstenberg, J Anal Math 34 pp 275– (1978)
[13]	Furstenberg, J Anal Math 45 pp 117– (1985)
[14]	Furstenberg, J Anal Math 57 pp 64– (1991) · Zbl 0770.05097
[15]	Hypergraph regularity and the multidimensional Szemerédi theorem, submitted.
[16]	Quasirandomness, counting and regularity for 3-uniform hypergraphs, Combin Probab Comput, to appear.
[17]	Gowers, Geom Funct Anal 11 pp 465– (2001)
[18]	Hales, Trans Am Math Soc 106 pp 222– (1963)
[19]	Haxell, J Combin Theory, Series A 113 pp 67– (2006)
[20]	, , An algorithmic version of a hypergraph regularity method, 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 23–25 October, 2005, Pittsburgh, PA, IEEE Computer Society, 2005, pp. 439–448.
[21]	Haxell, Random Struct Algor 22 pp 248– (2003)
[22]	, , Efficient testing of hypergraphs, Automata, Languages and Programming, 29th International Colloquium, ICALP 2002, Malaga, Spain, July 8–13, 2002, Proceedings ( , , , , , editors), Lecture Notes in Computer Science, vol. 2380, Springer-Verlag, 2002, pp. 1017–1028.
[23]	Kohayakawa, Combin Probab Comput 12 pp 155– (2003)
[24]	Kohayakawa, J Combin Theory A 97 pp 307– (2002)
[25]	, , , The regularity lemma and its applications in graph theory, Theoretical aspects of computer science (Tehran 2000), Lecture Notes in Computer Science, vol. 2292, Springer-Verlag, Berlin, 2002, pp. 84–112.
[26]	, Szemerédi’s regularity lemma and its applications in graph theory, Combinatorics, Paul Erdos is eighty, Vol. 2 (Keszthely, 1993), Bolyai Soc Math Stud, vol. 2, János Bolyai Math Soc, Budapest, 1996, pp. 295–352. MR 97d:05172.
[27]	Nagle, Discrete Math 235 pp 271– (2001)
[28]	Nagle, Random Struct Algor 23 pp 264– (2003)
[29]	, , Extremal hypergraph problems and the regularity method, to appear. · Zbl 1116.05041
[30]	, , A short proof of the 3-graph counting lemma, submitted.
[31]	Peng, Combin Probab Comput 14 pp 371– (2005)
[32]	Prömel, Random Struct Algor 3 pp 19– (1992)
[33]	Some developments in Ramsey theory, Proceedings of the International Congress of Mathematicians, Vol. I, II (Kyoto, 1990) (Tokyo), Math Soc Japan, 1991, pp. 1455–1466.
[34]	Rödl, J Combin Theory A 81 pp 1– (1998)
[35]	, , Dirac’s theorem for 3-uniform hypergraphs, Combin Probab Comput, to appear.
[36]	, Regular partitions of hypergraphs, submitted.
[37]	, , , Integer and fractional packings of hypergraphs, submitted. · Zbl 1111.05082
[38]	, , , Density theorems and extremal hypergraph problems, Israel J Math, to appear. · Zbl 1127.05055
[39]	, Applications of the regularity lemma for uniform hypergraphs, Random Struct Algor, to appear.
[40]	Rödl, Random Struct Algor 25 pp 1– (2004)
[41]	Rödl, Random Struct Algor 26 pp 160– (2005)
[42]	Roth, C. R. Acad. Sci Paris 234 pp 388– (1952)
[43]	Roth, J London Math Soc 28 pp 104– (1953)
[44]	, Triple systems with no six points carrying three triangles, Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II, North-Holland, Amsterdam, 1978, pp. 939–945.
[45]	Sárközy, Erdos and Sós, Discrete Math 297 pp 190– (2005)
[46]	On the regularity method for hypergraphs, Ph.D. thesis, Department of Mathematics and Computer Science, Emory University, May 2004.
[47]	Arithmetic progressions in sets with small sumsets, Combin Probab Comput, to appear. · Zbl 1147.11011
[48]	Dense arrangements are locally very dense II, manuscript. · Zbl 1122.52008
[49]	Note on a generalization of Roth’s theorem, Discrete and computational geometry, Algorithms Combin, vol. 25, Springer-Verlag, Berlin, 2003, pp. 825–827.
[50]	Solymosi, Combin Probab Comput 13 pp 263– (2004)
[51]	Szemerédi, Acta Arith 27 pp 199– (1975)
[52]	Regular partitions of graphs, Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), CNRS, Paris, 1978, pp. 399–401.
[53]	A quantitative ergodic theory proof of Szemerédi’s theorem, submitted.