Hypergraph regularity and the multidimensional Szemerédi theorem
From MaRDI portal
Publication:2482877
DOI10.4007/ANNALS.2007.166.897zbMATH Open1159.05052arXiv0710.3032OpenAlexW2149054878WikidataQ55881476 ScholiaQ55881476MaRDI QIDQ2482877FDOQ2482877
Authors: W. Timothy Gowers 
Publication date: 25 April 2008
Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/0710.3032
Recommendations
Random graphs (graph-theoretic aspects) (05C80) Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Generalized Ramsey theory (05C55) Hypergraphs (05C65) Ramsey theory (05D10) General groups of measure-preserving transformations (28D15)
Cited In (only showing first 100 items - show all)
- A Multipartite Version of the Hajnal–Szemerédi Theorem for Graphs and Hypergraphs
- Title not available (Why is that?)
- Packing \(k\)-partite \(k\)-uniform hypergraphs
- On the Chromatic Thresholds of Hypergraphs
- Multiple recurrence in quasirandom groups
- Additive combinatorics: with a view towards computer science and cryptography -- an exposition
- On replica symmetry of large deviations in random graphs
- Finite order spreading models
- Testability and repair of hereditary hypergraph properties
- Deducing the multidimensional Szemerédi theorem from an infinitary removal lemma
- Graph norms and Sidorenko's conjecture
- Independent sets in hypergraphs
- Hypergraph limits: A regularity approach
- The poset of hypergraph quasirandomness
- Sparse partition universal graphs for graphs of bounded degree
- Combinatorial theorems in sparse random sets
- Exact minimum degree thresholds for perfect matchings in uniform hypergraphs
- An approximate logic for measures
- A measure-theoretic approach to the theory of dense hypergraphs
- A geometric theory for hypergraph matching
- Generalizations of the removal lemma
- Sum-avoiding sets in groups
- Improved monochromatic loose cycle partitions in hypergraphs
- Hereditary properties of hypergraphs
- Hypergraph Independent Sets
- Regular hypergraphs, Gordon's lemma, Steinitz' lemma and invariant theory
- On the algebraic and topological structure of the set of Turán densities
- Quasirandom-Forcing Orientations of Cycles
- Weak hypergraph regularity and linear hypergraphs
- Testable and untestable classes of first-order formulae
- Hamilton \(\ell \)-cycles in uniform hypergraphs
- 3-uniform hypergraphs of bounded degree have linear Ramsey numbers
- Turán number of bipartite graphs with no \(K_{t,t}\)
- Density theorems and extremal hypergraph problems
- A tight bound for hypergraph regularity
- σ-algebras for quasirandom hypergraphs
- Edge distribution and density in the characteristic sequence
- A new proof of the density Hales-Jewett theorem
- Eigenvalues and linear quasirandom hypergraphs
- A density version of the Carlson-Simpson theorem
- Counting substructures. II: Hypergraphs
- Analytic methods for uniform hypergraphs
- Regular slices for hypergraphs
- Online containers for hypergraphs, with applications to linear equations
- Roth-type theorems in finite groups
- Minimum degree conditions for tight Hamilton cycles
- The hypergraph regularity method and its applications
- A relative Szemerédi theorem
- Erdős-Hajnal-type theorems in hypergraphs
- A variant of the hypergraph removal lemma
- Monochromatic Hamiltonian Berge-cycles in colored complete uniform hypergraphs
- Loose Hamilton cycles in hypergraphs
- A new proof of the graph removal lemma
- Ramsey numbers of sparse hypergraphs
- Tiling multipartite hypergraphs in quasi-random hypergraphs
- Extremal results in sparse pseudorandom graphs
- An approximate version of Sidorenko's conjecture
- The (7, 4)-Conjecture in Finite Groups
- Embedding and Ramsey numbers of sparse \(k\)-uniform hypergraphs
- From harmonic analysis to arithmetic combinatorics
- Szemerédi's regularity lemma via martingales
- The 3-colour Ramsey number of a 3-uniform Berge cycle
- A combinatorial proof of the removal lemma for groups
- A hypergraph regularity method for generalized Turán problems
- The NOF multiparty communication complexity of composed functions
- On the KŁR conjecture in random graphs
- The quasi-randomness of hypergraph cut properties
- Bounding the number of hyperedges in friendship \(r\)-hypergraphs
- A removal lemma for systems of linear equations over finite fields
- Quasirandom Latin squares
- Saturating Sperner families
- A hypergraph blow-up lemma
- Weak quasi-randomness for uniform hypergraphs
- Szemerédi's theorem, frequent hypercyclicity and multiple recurrence
- Turán number of generalized triangles
- Tight cycles and regular slices in dense hypergraphs
- Sparse hypergraphs: new bounds and constructions
- Quasirandom permutations are characterized by 4-point densities
- Proof of the Brown-Erdős-Sós conjecture in groups
- No additional tournaments are quasirandom-forcing
- On 3‐graphs with no four vertices spanning exactly two edges
- Regular partitions of gentle graphs
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- Finite reflection groups and graph norms
- Subsets of without L-shaped configurations
- Dirac-type theorems in random hypergraphs
- A polynomial regularity lemma for semialgebraic hypergraphs and its applications in geometry and property testing
- Characterization of quasirandom permutations by a pattern sum
- Ramsey classes of topological and metric spaces
- Cut distance identifying graphon parameters over weak* limits
- Keisler's order is not simple (and simple theories may not be either)
- Density and regularity theorems for semi-algebraic hypergraphs
- Random Simplicial Complexes: Models and Phenomena
- Testing Linear-Invariant Non-linear Properties: A Short Report
- Gowers uniformity norm and pseudorandom measures of the pseudorandom binary sequences
- Formalising Szemerédi's Regularity Lemma and Roth's Theorem on Arithmetic Progressions in Isabelle/HOL
- Tournament quasirandomness from local counting
- Removal lemmas and approximate homomorphisms
- The number of \(k\)-dimensional corner-free subsets of grids
- Arithmetic progressions, different regularity lemmas and removal lemmas
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)
