In mathematics, the hypergraph regularity method is a powerful tool in extremal graph theory that refers to the combined application of the hypergraph regularity lemma and the associated counting lemma.
Very informally, the hypergraph regularity lemma decomposes any given
-uniform hypergraph into a random-like object with bounded parts (with an appropriate boundedness and randomness notions) that is usually easier to work with.
On the other hand, the hypergraph counting lemma estimates the number of hypergraphs of a given isomorphism class in some collections of the random-like parts.
This is an extension of Szemerédi's regularity lemma that partitions any given graph into bounded number parts such that edges between the parts behave almost randomly.
Similarly, the hypergraph counting lemma is a generalization of the graph counting lemma that estimates number of copies of a fixed graph as a subgraph of a larger graph.
There are several distinct formulations of the method, all of which imply the hypergraph removal lemma and a number of other powerful results, such as Szemerédi's theorem, as well as some of its multidimensional extensions.
The following formulations are due to V. Rödl, B. Nagle, J. Skokan, M. Schacht, and Y. Kohayakawa,[1] for alternative versions see Tao (2006),[2] and Gowers (2007).
[3] In order to state the hypergraph regularity and counting lemmas formally, we need to define several rather technical terms to formalize appropriate notions of pseudo-randomness (random-likeness) and boundedness, as well as to describe the random-like blocks and partitions.
The following defines an important notion of relative density, which roughly describes the fraction of
is equal to the fraction of triangles formed by 2-edges in the subhypergraph that are 3-edges.
.What follows is the appropriate notion of pseudorandomness that the regularity method will use.
More precisely, this defines a setting where density of
edges in large subhypergraphs is roughly the same as one would expect based on the relative density alone.
.Roughly speaking, the following describes the pseudorandom blocks into which the hypergraph regularity lemma decomposes any large enough hypergraph.
More precisely, this defines a notion of regular hypergraph called
Moreover, the density of 3-edges over all possible triangles made by 2-edges is roughly the same in every collection of subhypergraphs.Definition [
Given vectors of positive real numbers
-regular if The following describes the equitable partition that the hypergraph regularity lemma will induce.
In fact, Gowers[3] demonstrated that solely vertex partition can not give a sufficiently strong notion of regularity to imply Hypergraph counting lemma.
In particular, this is the main definition that describes the output of hypergraph regularity lemma below.Definition [Regularity with respect to a partition].
vertices, there exists a family of partitions
The main application through which most others follow is the hypergraph removal lemma, which roughly states that given fixed
One of the original motivations for graph regularity method was to prove Szemerédi's theorem, which states that every dense subset of
contains an arithmetic progression of arbitrary length.
In fact, by a relatively simple application of the triangle removal lemma, one can prove that every dense subset of
The hypergraph regularity method and hypergraph removal lemma can prove high-dimensional and ring analogues of density version of Szemerédi's theorems, originally proved by Furstenberg and Katznelson.
[4] In fact, this approach yields first quantitative bounds for the theorems.
This theorem roughly implies that any dense subset of
.Another possible generalization that can be proven by the removal lemma is when the dimension is allowed to grow.Let