Hostname: page-component-74656f9884-rdgjk Total loading time: 0 Render date: 2026-11-08T15:06:53.451Z Has data issue: false hasContentIssue false
  • English
  • Français

Regular Partitions of Hypergraphs: Regularity Lemmas

Published online by Cambridge University Press:  01 November 2007

VOJTĚCH RÖDL  and
MATHIAS SCHACHT
VOJTĚCH RÖDL
Affiliation:
Department of Mathematics and Computer Science, Emory University, Atlanta, GA 30322, USA (e-mail: rodl@mathcs.emory.edu)
MATHIAS SCHACHT
Affiliation:
Institut für Informatik, Humboldt-Universität zu Berlin, Unter den Linden 6, 10099 Berlin, Germany (e-mail: schacht@informatik.hu-berlin.de)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Szemerédi's regularity lemma for graphs has proved to be a powerful tool with many subsequent applications. The objective of this paper is to extend the techniques developed by Nagle, Skokan, and the authors and obtain a stronger and more ‘user-friendly’ regularity lemma for hypergraphs.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 16 , Issue 6 , November 2007 , pp. 833 - 885
Copyright
Copyright © Cambridge University Press 2007

References

[1]Alon, N., Fischer, E., Krivelevich, M. and Szegedy, M. (2000) Efficient testing of large graphs. Combinatorica 20 451–476.CrossRefGoogle Scholar
[2]Avart, C., Rödl, V. and Schacht, M.Every monotone 3-graph property is testable. SIAM J. Discrete Math. 21 (1)73–92.CrossRefGoogle Scholar
[3]Cooley, O., Fountoulakis, N., Kühn, D. and Osthus, D. Embeddings and R amsey numbers of sparse k-uniform hypergraphs. Submitted.Google Scholar
[4]Eroődos, P., Frankl, P. and Rödl, V. (1986) The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent. Graphs Combin. 2 113–121.Google Scholar
[5]Frankl, P. and Rödl, V. (2002) Extremal problems on set systems. Random Struct. Alg. 20 131–164.CrossRefGoogle Scholar
[6]Friedgut, E., Rödl, V., Ruciński, A. and Tetali, P. (2006) A sharp threshold for random graphs with a monochromatic triangle in every edge coloring. Mem. Amer. Math. Soc. 179 845.Google Scholar
[7]Furstenberg, H. and Katznelson, Y. (1978) An ergodic Szemerédi theorem for commuting transformations. J. Analyse Math. 34 275–291.CrossRefGoogle Scholar
[8]Furstenberg, H. and Katznelson, Y. (1985) An ergodic Szemerédi theorem for IP-systems and combinatorial theory. J. Analyse Math. 45 117–168.CrossRefGoogle Scholar
[9]Furstenberg, H. and Katznelson, Y. (1991) A density version of the Hales–Jewett theorem. J. Anal. Math. 57 64–119.CrossRefGoogle Scholar
[10]Gowers, W. T. Hypergraph regularity and the multidimensional Szemerédi theorem. Submitted.Google Scholar
[11]Gowers, W. T. (1997) Lower bounds of tower type for Szemerédi's uniformity lemma. Geom. Funct. Anal. 7 322–337.CrossRefGoogle Scholar
[12]Gowers, W. T. (2006) Quasirandomness, counting and regularity for 3-uniform hypergraphs. Combin. Probab. Comput. 15 143–184.Google Scholar
[13]Green, B. (2005) A Szemerédi-type regularity lemma in abelian groups, with applications. Geom. Funct. Anal. 15 340–376.Google Scholar
[14]Green, B. and Tao, T.The primes contain arbitrarily long arithmetic progressions. Ann. of Math. (2), to appear.Google Scholar
[15]Hales, A. W. and Jewett, R. I. (1963) Regularity and positional games. Trans. Amer. Math. Soc. 106 222–229.Google Scholar
[16]Kohayakawa, Y. (1997) Szemerédi's regularity lemma for sparse graphs. In Foundations of Computational Mathematics: Rio de Janeiro 1997, Springer, Berlin, pp. 216–230.CrossRefGoogle Scholar
[17]Kohayakawa, Y., Rödl, V. and Skokan, J. (2002) Hypergraphs, quasi-randomness, and conditions for regularity. J. Combin. Theory Ser. A 97 307–352.Google Scholar
[18]Komlós, J., Shokoufandeh, A., Simonovits, M. and Szemerédi, E. (2002) The regularity lemma and its applications in graph theory. In Theoretical Aspects of Computer Science: Tehran 2000, Vol. 2292 of Lecture Notes in Computer Science, Springer, Berlin, pp. 84–112.Google Scholar
[19]Komlós, J. and Simonovits, M. (1996) Szemerédi's regularity lemma and its applications in graph theory. In Combinatorics: Paul Erd\H os is Eighty, Vol. 2 (Keszthely 1993), Vol. 2 of Bolyai Soc. Math. Stud., János Bolyai Math. Soc., Budapest, pp. 295–352.Google Scholar
[20]Nagle, B., Rödl, V. and Schacht, M. (2006) The counting lemma for regular k-uniform hypergraphs. Random Struct. Alg. 28 113–179.Google Scholar
[21]Nagle, B., Rödl, V. and Schacht, M. (2006) Extremal hypergraph problems and the regularity method. In Topics in Discrete Mathematics, Vol. 26 of Algorithms Combin., Springer, Berlin, pp. 247–278.CrossRefGoogle Scholar
[22]Nagle, B., Sayaka, O., Rödl, V. and Schacht, M. On the Ramsey number of sparse 3-graphs. Submitted.Google Scholar
[23]Rödl, V. and Schacht, M. (2007) Regular partitions of hypergraphs: counting lemmas. Combin. Probab. Comput. 16 (6): 887–901.Google Scholar
[24]Rödl, V., Schacht, M., Siggers, M. and Tokushige, N. (2007) Integer and fractional packings of hypergraphs. J. Combin. Theory Ser. B 97 245–268.Google Scholar
[25]Rödl, V., Schacht, M., Tengan, E. and Tokushige, N. (2006) Density theorems and extremal hypergraph problems. Israel J. Math. 152 371–380.CrossRefGoogle Scholar
[26]Rödl, V. and Skokan, J. (2004) Regularity lemma for k-uniform hypergraphs. Random Struct. Alg. 25 1–42.Google Scholar
[27]Rödl, V. and Skokan, J. (2006) Applications of the regularity lemma for uniform hypergraphs. Random Struct. Alg. 28 180–194.CrossRefGoogle Scholar
[28]Ruzsa, I. Z. and Szemerédi, E. (1978) Triple systems with no six points carrying three triangles. In Combinatorics: Proc. Fifth Hungarian Colloq, Vol. II (Keszthely 1976), Vol. 18 of Colloq. Math. Soc. János Bolyai, North-Holland, Amsterdam, pp. 939–945.Google Scholar
[29]Solymosi, J. (2004) A note on a question of Erdőos and Graham. Combin. Probab. Comput. 13 263–267.CrossRefGoogle Scholar
[30]Szemerédi, E. (1975) On sets of integers containing no k elements in arithmetic progression. Acta Arith. 27 199–245.CrossRefGoogle Scholar
[31]Szemerédi, E. (1978) Regular partitions of graphs. In Problèmes Combinatoires et Théorie des Graphes: Colloq. Internat. CNRS, Univ. Orsay, Orsay 1976, Vol. 260 of Colloq. Internat. CNRS, CNRS, Paris, pp. 399–401.Google Scholar
[32]Tao, T. (2006) A variant of the hypergraph removal lemma. J. Combin. Theory Ser. A 113 1257–1280.Google Scholar