Hypergraph regularity and the multidimensional Szemerédi theorem

Abstract

We prove analogues for hypergraphs of Szemerédi's regularity lemma and the associated counting lemma for graphs. As an application, we give the first combinatorial proof of the multidimensional Szemerédi theorem of Furstenberg and Katznelson, and the first proof that provides an explicit bound. Similar results with the same consequences have been obtained independently by Nagle, Rödl, Schacht and Skokan.

53 pages

Cited by in corpus (29)

• Hamilton l-cycles in uniform hypergraphs
• Loose Hamilton cycles in hypergraphs
• Extremal results in sparse pseudorandom graphs
• On the testability and repair of hereditary hypergraph properties
• The dichotomy between structure and randomness, arithmetic progressions, and the primes
• Expanding polynomials over finite fields of large characteristic, and a regularity lemma for definable sets
• Norm convergence of multiple ergodic averages for commuting transformations
• A Simple Regularization of Hypergraphs
• The number of hypergraphs and colored Hypergraphs with hereditary properties
• Embeddings and Ramsey numbers of sparse k-uniform hypergraphs
• A correspondence principle between (hyper)graph theory and probability theory, and the (hyper)graph removal lemma
• Removal lemma for infinitely-many forbidden hypergraphs and property testing
• On the Number of 2-SAT Functions
• Convergence of multiple ergodic averages
• Keisler's order is not simple (and simple theories may not be either)
• An approximate version of Sidorenko's conjecture
• 3-Uniform hypergraphs of bounded degree have linear Ramsey numbers
• $F$-factors in Quasi-random Hypergraphs
• Three Dimensional Corners: A Box Norm Proof
• Packing k-partite k-uniform hypergraphs
• The Poset of Hypergraph Quasirandomness
• Resilience for tight Hamiltonicity
• On generalizations of Gowers norms and their geometry
• Bounding the Number of Hyperedges in Friendship $r$-Hypergraphs
• On Gowers norms of some functions
• The prime ideals in every class contain arbitrary large truncated classes
• Tiling multipartite hypergraphs in Quasi-random Hypergraphs
• Removal lemmas and approximate homomorphisms
• The number of 3-SAT functions