Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-23T13:31:22.447Z 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: [email protected])
MATHIAS SCHACHT
Affiliation:
Institut für Informatik, Humboldt-Universität zu Berlin, Unter den Linden 6, 10099 Berlin, Germany (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

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

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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