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 Nagle, Rödl, Schacht and Skokan and, independently, by Gowers.

The hypergraph removal lemma can be used to prove results such as Szemerédi's theorem and the multi-dimensional Szemerédi theorem.

Let ${\displaystyle H}$ be a ${\displaystyle r}$-uniform (every edge connects exactly r vertices) hypergraph with ${\displaystyle h}$ vertices. The hypergraph removal lemma states that for any ${\displaystyle \varepsilon >0}$ there exists ${\displaystyle \delta =\delta (r,m,\varepsilon )>0}$ such that for any ${\displaystyle r}$-uniform, ${\displaystyle n}$-vertex hypergraph ${\displaystyle G}$ with fewer than ${\displaystyle \delta n^{h}}$ subhypergraphs isomorphic to ${\displaystyle H}$ it is possible to remove all copies of ${\displaystyle H}$ by removing at most ${\displaystyle \varepsilon n^{r}}$ edges.

An equivalent formulation is that, for any hypergraph ${\displaystyle G}$ with ${\displaystyle o(n^{h})}$ copies of ${\displaystyle H}$, we can eliminate all copies of ${\displaystyle H}$ from ${\displaystyle G}$ by removing ${\displaystyle o(n^{r})}$ hyperedges.

Graph removal lemma is a special case with ${\displaystyle r=2}$.

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 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.

In Szemerédi's regularity lemma, the partitions are performed on vertices (1-hyperedge) to regulate edges (2-hyperedge). However, for ${\displaystyle k>2}$, if we simply regulate ${\displaystyle k}$-hyperedges using only 1-hyperedge, we will lose information of all ${\displaystyle j}$-hyperedges in the middle where ${\displaystyle 1<j<k}$, and fail to find a counting lemma. The correct version has to partition ${\displaystyle (k-1)}$-hyperedges in order to regulate ${\displaystyle k}$-hyperedges. To gain more control of the ${\displaystyle (k-1)}$-hyperedges, we can go a level deeper and partition on ${\displaystyle (k-2)}$-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${\displaystyle E(K_{n})=G_{1}^{(2)}\cup \dots \cup G_{l}^{(2)}}$ such that for most triples ${\displaystyle (i,j,k),}$ there are a lot of triangles on top of ${\displaystyle \left(G_{i}^{(2)},G_{j}^{(2)},G_{k}^{(2)}\right).}$ We say that ${\displaystyle \left(G_{i}^{(2)},G_{j}^{(2)},G_{k}^{(2)}\right)}$ is "pseudorandom" in the sense that for all subgraphs ${\displaystyle A_{i}^{(2)}\subset G_{i}^{(2)}}$ with not too few triangles on top of ${\displaystyle \left(A_{i}^{(2)},A_{j}^{(2)},A_{k}^{(2)}\right),}$ we have