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. The special case in which the graph is a tetrahedron is known as the tetrahedron removal lemma. It was first proved by Gowers and, independently, by Nagle, Rödl, Schacht and Skokan. The hypergraph removal lemma can be used to prove, for instance, Szemerédi's theorem, and multi-dimensional Szemerédi's theorem.
Statement
Let be any -regular hypergraph with vertices. The hypergraph removal lemma states that for any, there exists such that the following is true: if is any -vertex -regular hypergraph with at most subgraphs isomorphic to, then it is possible to eliminate all copies of from by removing at most hyperedges from. An equivalent formulation is that, for any graph with copies of, we can eliminate all copies of from by removing hyperedges.
Proof idea
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 and a counting lemma. The key difficulty in the proof is to define the correct notion of hypergraph regularity. There were multiple attempts to define "partition" and "pseudorandom 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. In Szemerédi's regularity lemma, the partitions are performed on vertices to regulate edges. However, for, if we simply regulate -hyperedges using only 1-hyperedge, we will lose information of all -hyperedges in the middle where, and fail to find a counting lemma. The correct version has to partition -hyperedges in order to regulate -hyperedges. To gain more control of the -hyperedges, we can go a level deeper and partition on -hyperedges to regulate them, etc. 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. Consider a partition of edges such that for most triples there are a lot of triangles on top of We say that is "pseudorandom" in the sense that for all subgraphs with not too few triangles on top of 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. In addition to this, we need to further regularize via a partition of the vertex set. As a result, we have the total data of hypergraph regularity as follows:
a partition of into graphs such that sits pseudorandomly on top;
a partition of such that the graphs in are extremely pseudorandom.
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.
Proof of Szemerédi's theorem
Let be the size of the largest subset of that does not contain a length arithmetic progression. Szemerédi's theorem states that, for any constant. 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. Let be a subset that does not contain any length arithmetic progression. Let be a large enough integer. We can think of as a subset of. Clearly, if doesn't have length arithmetic progression in, it also doesn't have length arithmetic progression in. We will construct a -partite -regular hypergraph from with parts, all of which are element vertex sets indexed by. For each, we add a hyperedge among vertices if and only if Let be the complete -partite -regular hypergraph. If contains an isomorphic copy of with vertices, then for any. However, note that is a length arithmetic progression with common difference. Since has no length arithmetic progression, it must be the case that, so. Thus, for each hyperedge, we can find a unique copy of that this edge lies in by finding. The number of copies of in equals. Therefore, by the hypergraph removal lemma, we can remove edges to eliminate all copies of in. Since every hyperedge of is in a unique copy of, to eliminate all copies of in, we need to remove at least edges. Thus,. The number of hyperedges in is, which concludes that. 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, Gowers proved that for some constant depending on. It is the best bound for so far.
Applications
The hypergraph removal lemma is used to prove the multidimensional Szemerédi theorem by J. Solymosi. The statement is that any for any finite subset of, any and any large enough, any subset of of size at least contains a subset of the form, that is, a dilated and translated copy of. Corners theorem is a special case when.
It is also used to prove the polynomial Szemerédi theorem, the finite field Szemerédi theorem and the finite abelian group Szemerédi theorem.
