Hypergraph regularity and the multidimensional Szemerédi theorem

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

• Regularity, uniformity, and quasirandomness
• The hypergraph regularity method and its applications
• The counting lemma for regular k‐uniform hypergraphs
• A tight bound for hypergraph regularity
• Regular Partitions of Hypergraphs: Regularity Lemmas

zbMATH Keywords

Regularity LemmaFurstenberg-Katznelson's theoremRemoval Lemmamultidimensional Szemerédi theorem

Mathematics Subject Classification ID

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)

• 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
• A multidimensional Szemerédi theorem in the primes via combinatorics
• A sparse regular approximation lemma
• On the Gowers norms of certain functions
• Hypergraphs without exponents
• Hypergraph removal lemmas via robust sharp threshold theorems
• The number of 3-SAT functions
• Lower bound on the size of a quasirandom forcing set of permutations
• Green's conjecture and testing linear invariant properties
• Uniformity norms, their weaker versions, and applications
• Hypergraph based Berge hypergraphs
• An analytic approach to sparse hypergraphs: hypergraph removal
• The Gaussian primes contain arbitrarily shaped constellations
• A new bound for the Brown-Erdős-Sós problem
• The junta method for hypergraphs and the Erdős-Chvátal simplex conjecture
• Weak hypergraph regularity and applications to geometric Ramsey theory
• Generalizations of Fourier analysis, and how to apply them
• Concentration estimates for functions of finite high‐dimensional random arrays
• Number on the forehead protocols yielding dense Ruzsa-Szemerédi graphs and hypergraphs
• An arithmetic transference proof of a relative Szemerédi theorem
• F$F$‐factors in Quasi‐random Hypergraphs
• Note on the 3-graph counting Lemma
• Mixing for progressions in nonabelian groups.
• Szemerédi's proof of Szemerédi's theorem
• On arithmetic progressions in symmetric sets in finite field model
• Diagonal Ramsey via effective quasirandomness
• Additive combinatorics and graph theory
• Constructive packings by linear hypergraphs
• Testing Linear-Invariant Properties
• Edge correlations in Random regular hypergraphs and applications to subgraph testing
• Hypergraph regularity and random sampling
• On graph norms for complex‐valued functions
• Quasi-random Boolean functions
• Corners over quasirandom groups
• Title not available (Why is that?)
• A blurred view of Van der Waerden type theorems
• Resilience for tight Hamiltonicity
• Some Cubic Time Regularity Algorithms for Triple Systems
• Factors and loose Hamilton cycles in sparse pseudo‐random hypergraphs
• On some extremal results for order types
• Linear quasi-randomness of subsets of abelian groups and hypergraphs
• Local-vs-global combinatorics
• Restricted problems in extremal combinatorics
• An improved bound for regular decompositions of 3-uniform hypergraphs of bounded \(\mathrm{VC}_2\)-dimension
• Forcing generalised quasirandom graphs efficiently
• On the threshold for Szemerédi's theorem with random differences
• Colouring versus density in integers and Hales-Jewett cubes
• Equivalent regular partitions of three-uniform hypergraphs
• Induced Turán problem in bipartite graphs
• Patterns without a popular difference
• Interview with Larry Guth
• On random sampling in uniform hypergraphs
• Extremal independent set reconfiguration
• 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

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)