Hypergraph regularity and the multidimensional Szemerédi theorem
From MaRDI portal
Publication:2482877
Abstract: We prove analogues for hypergraphs of Szemer'edi's regularity lemma and the associated counting lemma for graphs. As an application, we give the first combinatorial proof of the multidimensional Szemer'edi 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"odl, Schacht and Skokan.
In recent years there is huge activity on how to generalize Szemerédi's Regularity and Removal lemmas for hypergraphs. There are different approaches, different results, even different definitions. (See for example [\textit{V. Rödl} and \textit{J. Skokan}, Random Struct. Algorithms 25, No. 1, 1--42 (2004; Zbl 1046.05042), \textit{B. Nagle}, \textit{V. Rödl}, and \textit{M. Schacht}, ibid. 28, 113--179 (2006; Zbl 1093.05045); \textit{T. Tao}, J. Comb. Theory, Ser. A 113, 1257--1280 (2006; Zbl 1105.05052 ); \textit{G. Elek} and \textit{B. Szegedy}, Limits of hypergraphs, regularity and removal lemmas. A non-standard approach. \url{http://arxiv1.library.cornell.edu/abs/0705.2179v1}]). The paper under review develops its own versions of the Regularity and Removal lemmas for hypergraphs, and as application it gives the first combinatorial proofs for the multidimensional Szemerédi theorem (and also providing an explicit bound).
Recommendations
Cited in
(only showing first 100 items - show all)- Hereditary properties of hypergraphs
- A combinatorial proof of the removal lemma for groups
- Regular hypergraphs, Gordon's lemma, Steinitz' lemma and invariant theory
- Additive combinatorics and graph theory
- A multidimensional Szemerédi theorem in the primes via combinatorics
- A removal lemma for systems of linear equations over finite fields
- On the Gowers norms of certain functions
- Finite order spreading models
- The number of 3-SAT functions
- An approximate logic for measures
- Tournament quasirandomness from local counting
- Hypergraphs without exponents
- Hypergraph based Berge hypergraphs
- A new bound for the Brown-Erdős-Sós problem
- No additional tournaments are quasirandom-forcing
- Cut distance identifying graphon parameters over weak* limits
- Dirac-type theorems in random hypergraphs
- The number of k-dimensional corner-free subsets of grids
- On arithmetic progressions in symmetric sets in finite field model
- Number on the forehead protocols yielding dense Ruzsa-Szemerédi graphs and hypergraphs
- Regular partitions of gentle graphs
- Szemerédi's proof of Szemerédi's theorem
- Sparse hypergraphs: new bounds and constructions
- The junta method for hypergraphs and the Erdős-Chvátal simplex conjecture
- Keisler's order is not simple (and simple theories may not be either)
- Analytic methods for uniform hypergraphs
- A tight bound for hypergraph regularity
- A relative Szemerédi theorem
- Finite reflection groups and graph norms
- Quasirandom permutations are characterized by 4-point densities
- Density theorems and extremal hypergraph problems
- Ramsey classes of topological and metric spaces
- Extremal results in sparse pseudorandom graphs
- Multiple recurrence in quasirandom groups
- Monochromatic Hamiltonian Berge-cycles in colored complete uniform hypergraphs
- The Gaussian primes contain arbitrarily shaped constellations
- 3-uniform hypergraphs of bounded degree have linear Ramsey numbers
- Roth-type theorems in finite groups
- On the algebraic and topological structure of the set of Turán densities
- Tiling multipartite hypergraphs in quasi-random hypergraphs
- Sum-avoiding sets in groups
- Additive combinatorics: with a view towards computer science and cryptography -- an exposition
- Mixing for progressions in nonabelian groups.
- Szemerédi's theorem, frequent hypercyclicity and multiple recurrence
- σ-algebras for quasirandom hypergraphs
- A polynomial regularity lemma for semialgebraic hypergraphs and its applications in geometry and property testing
- Testability and repair of hereditary hypergraph properties
- The 3-colour Ramsey number of a 3-uniform Berge cycle
- A hypergraph blow-up lemma
- Szemerédi's regularity lemma via martingales
- Weak quasi-randomness for uniform hypergraphs
- The quasi-randomness of hypergraph cut properties
- Gowers uniformity norm and pseudorandom measures of the pseudorandom binary sequences
- Generalizations of Fourier analysis, and how to apply them
- On replica symmetry of large deviations in random graphs
- Hypergraph limits: A regularity approach
- Regular slices for hypergraphs
- Online containers for hypergraphs, with applications to linear equations
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- Patterns without a popular difference
- Characterization of quasirandom permutations by a pattern sum
- Turán number of generalized triangles
- Combinatorial theorems in sparse random sets
- A hypergraph regularity method for generalized Turán problems
- Saturating Sperner families
- Improved monochromatic loose cycle partitions in hypergraphs
- A new proof of the density Hales-Jewett theorem
- Exact minimum degree thresholds for perfect matchings in uniform hypergraphs
- Testable and untestable classes of first-order formulae
- A measure-theoretic approach to the theory of dense hypergraphs
- A sparse regular approximation lemma
- An analytic approach to sparse hypergraphs: hypergraph removal
- On the KŁR conjecture in random graphs
- A density version of the Carlson-Simpson theorem
- Counting substructures. II: Hypergraphs
- scientific article; zbMATH DE number 878896 (Why is no real title available?)
- Hypergraph Independent Sets
- A Multipartite Version of the Hajnal–Szemerédi Theorem for Graphs and Hypergraphs
- Testing Linear-Invariant Non-linear Properties: A Short Report
- Green's conjecture and testing linear invariant properties
- Proof of the Brown-Erdős-Sós conjecture in groups
- The NOF multiparty communication complexity of composed functions
- Bounding the number of hyperedges in friendship \(r\)-hypergraphs
- Random Simplicial Complexes: Models and Phenomena
- Interview with Larry Guth
- Weak hypergraph regularity and applications to geometric Ramsey theory
- Uniformity norms, their weaker versions, and applications
- Testing Linear-Invariant Properties
- Turán number of bipartite graphs with no \(K_{t,t}\)
- Hypergraph removal lemmas via robust sharp threshold theorems
- Nonparametric modeling of higher-order interactions via hypergraphons
- Tight cycles and regular slices in dense hypergraphs
- On random sampling in uniform hypergraphs
- Edge correlations in Random regular hypergraphs and applications to subgraph testing
- Independent sets in hypergraphs
- The poset of hypergraph quasirandomness
- Density and regularity theorems for semi-algebraic hypergraphs
- The (7, 4)-Conjecture in Finite Groups
- On the Chromatic Thresholds of Hypergraphs
- Corners over quasirandom groups
This page was built for publication: Hypergraph regularity and the multidimensional Szemerédi theorem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2482877)
