Hypergraph regularity and the multidimensional Szemerédi theorem

By William T. Gowers. 2007

463 citations recorded by the source corpus.

We prove analogues for hypergraphs of Szemeredi's regularity lemma and the associated counting lemma for graphs. As an application, we give the first combinatorial proof of the multidimensional Szemeredi 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, Rodl, Schacht and Skokan.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/9c91d268755e325adcf390d8cc6046cd6e77ef16

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Discrete Mathematics and Combinatorics

In Geometry and Topology

Citations in the corpus

On exchangeable random variables and the statistics of large graphs and hypergraphs (2008, background): “orm hypergraphs, not just ordinary k-hypergraphs, that emerge naturally in the recent hypergraph regularity approaches to Szemer´edi’s Theorem (see, for example, Nagle, Ro¨dl and Schacht [53], Gowers [36] and Chapter 10 of Tao and Vu [64]). While the parallels between the structure theory for partit”
Decompositions, approximate structure, transference, and the Hahn–Banach theorem (2008, methodology): “These ideas can be developed to give a complete proof of Szemerédi’s theorem; see [8, 15, 17, 22].”
Independent sets in hypergraphs (2012, methodology): “Numerous partial results and special cases had been established by various researchers [24, 28, 31, 34, 35, 42, 44, 61] before the conjecture was finally proved by Conlon and Gowers [14] (under the assumption that H is strictly 2- balanced1) and by Schacht [58].”
A correspondence principle between (hyper)graph theory and probability theory, and the (hyper)graph removal lemma (2006, methodology): “We can now repeat the arguments from Section 4 to obtain the following triangle-removal lemma of Nagle, Schacht, R¨odl, and Skokan [19], [20], [22], [23] (and independently by Gowers [12]; see also [30] for a later proof): Theorem 8.1 (Hypergraph removal lemma) .”
Combinatorial theorems in sparse random sets (2010, background): “The dense result is due to Nagle, Rödl, Schacht and Skokan [40], [51], and independently to the second author [21].”
Analytic methods for uniform hypergraphs (2013, methodology): “We start by recalling the Hypergraph Removal Lemma, one of the most important consequences of the Hypergraph Regularity Lemma, proved independently by Gowers [14] and by Nagle, Rödl, Schacht and Skokan [25], [36].”
On the KŁR conjecture in random graphs (2013, background): “The main obstacle here is to prove a sparse counterpart to the hypergraph regularity lemma [37, 38, 65, 74, 84].”
Diagonal Ramsey via effective quasirandomness (2020, background): “with potentially tow(ε−c) pieces needed [11] (here tow means taking an exponential tower of 2’s of the speciﬁed length). Much attention has been given to generalizing this result to hypergraphs (e.g. [17, 12]) and sparse graphs (e.g. [10, 1, 3, 19, 6, 7]) in connection with extremal graph theory and”
Surveys in Combinatorics 2011: Hypergraph Turán problems (2011, unknown): “[148, 163, 162] and Gowers [89].”
Sparse partition universal graphs for graphs of bounded degree (2011, background): “Consequently, the so called size-Ramsey number of any H with n vertices and maximum degree ∆ is O(n2−1/∆ log1/∆ n).”