Regularity Lemma for k‐uniform hypergraphs

By Vojtech Rödl, Jozef Skokan. Random Struct. Algorithms, 2004

301 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics

View Paper: https://www.semanticscholar.org/paper/f087969af2a702951cbbc4437069a8413cdee18d

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

Citations in the corpus

Surveys in Combinatorics 2009: Embedding large subgraphs into dense graphs (2009, background): “The first so-called ‘strong’ versions for r-uniform hypergraphs were proved in [48] and [107, 119].”
Hypergraph regularity and the multidimensional Szemerédi theorem (2007, methodology): “The main results of this paper have been obtained independently by Nagle, R¨ odl, Schacht and Skokan [NRS, RS ].”
Decompositions, approximate structure, transference, and the Hahn–Banach theorem (2008, background): “These ideas can be developed to give a complete proof of Szemerédi’s theorem; see [8, 15, 17, 22].”
Graph norms and Sidorenko’s conjecture (2008, background): “Recently Gowers [13, 14] defined a hypergraph version of this norm, and subsequently he [12] and Nagle, Rödl, Schacht, and Skokan [22, 26, 25] independently established a hypergraph regularity lemma which easily implies Szemerédi’s theorem in its full generality, and even stronger theorems such as F”
Limits of Hypergraphs, Removal and Regularity Lemmas. A Non-standard Approach (2007, background): “The so-called Hypergraph Regularity Lemma (Rödl-Skokan [9], Gowers [2], later generalized by Tao [11]) is one of the most exciting result in modern combinatorics.”
Sparse partition universal graphs for graphs of bounded degree (2011, methodology): “Thanks to recent advances [18, 30, 34], one is now able to apply the regularity method to hypergraphs; for instance, one may now give a fully combinatorial proof of theorems such as the Furstenberg–Katznelson theorem [15] on the existence of homothetic copies of finite configurations in dense subset”
The Gaussian primes contain arbitrarily shaped constellations (2005, unknown): “It also follows from the hypergraph analysis of Gowers [8] and R¨odl-Sko ka n [14], [15], or more precisely from Theorem 1.7 below.”
A Geometric Theory for Hypergraph Matching (2011, background): “[15,43,50,52], and the recent hypergraph blowup lemma of Keevash [22].”
A relative Szemerédi theorem (2013, methodology): “This is a strengthening of an earlier theorem used by Tao in his proof that the Gaussian primes contain arbitrarily shaped constellations and, by standard arguments, allows us to deduce the relative Szemerédi theorem.”
A proof of a conjecture of Buck, Chan, and Robbins on the expected value of the minimum assignment (2005, background): “Theorem 7.15 in [ RS04 ]), we may assume the following order of constants that is guaranteed by this Lemma.”
A measure-theoretic approach to the theory of dense hypergraphs (2008, background): “Now we are ready to state the Hypergraph Regularity Lemma for k-uniform hypergraphs (see [5,7,14,15,18]).”