In graph theory, the hypergraph removal lemma states that when a hypergraph contains few copies of a given sub-hypergraph, then all of the copies can be eliminated by removing a small number of hyperedges.
It is a generalization of the graph removal lemma.
It was first proved by Nagle, Rödl, Schacht and Skokan[1] and, independently, by Gowers.
[2] The hypergraph removal lemma can be used to prove results such as Szemerédi's theorem[1] and the multi-dimensional Szemerédi theorem.
-uniform (every edge connects exactly r vertices) hypergraph with
The hypergraph removal lemma states that for any
An equivalent formulation is that, for any hypergraph
Graph removal lemma is a special case with
The high level idea of the proof is similar to that of graph removal lemma.
We prove a hypergraph version of Szemerédi's regularity lemma (partition hypergraphs into pseudorandom blocks) and a counting lemma (estimate the number of hypergraphs in an appropriate pseudorandom block).
The key difficulty in the proof is to define the correct notion of hypergraph regularity.
There were multiple attempts[3][4][5][6][7][8][9][10][11][12] to define "partition" and "pseudorandom (regular) blocks" in a hypergraph, but none of them are able to give a strong counting lemma.
The first correct definition of Szemerédi's regularity lemma for general hypergraphs is given by Rödl et al.[1] In Szemerédi's regularity lemma, the partitions are performed on vertices (1-hyperedge) to regulate edges (2-hyperedge).
, and fail to find a counting lemma.
In the end, we will reach a complex structure of regulating hyperedges.
For example, we demonstrate an informal 3-hypergraph version of Szemerédi's regularity lemma, first given by Frankl and Rödl.
is "pseudorandom" in the sense that for all subgraphs
we have We then subsequently define a regular partition as a partition in which the triples of parts that are not regular constitute at most an
fraction of all triples of parts in the partition.
As a result, we have the total data of hypergraph regularity as follows: After proving the hypergraph regularity lemma, we can prove a hypergraph counting lemma.
The rest of proof proceeds similarly to that of Graph removal lemma.
Szemerédi's theorem states that,
The high level idea of the proof is that, we construct a hypergraph from a subset without any length
arithmetic progression, then use graph removal lemma to show that this graph cannot have too many hyperedges, which in turn shows that the original subset cannot be too big.
element vertex sets indexed by
arithmetic progression with common difference
arithmetic progression, it must be the case that
that this edge lies in by finding
This method usually does not give a good quantitative bound, since the hidden constants in hypergraph removal lemma involves the inverse Ackermann function.
For a better quantitive bound, Leng, Sah, and Sawhney proved that