Hypergraph removal lemma

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 ^[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. ^[1]

Statement

The hypergraph removal lemma states that for any ${\displaystyle \varepsilon ,r,m>0}$, there exists ${\displaystyle \delta =\delta (\varepsilon ,r,m)>0}$ such that for any ${\displaystyle r}$-uniform hypergraph ${\displaystyle H}$ with ${\displaystyle m}$ vertices the following is true: if ${\displaystyle G}$ is any ${\displaystyle n}$-vertex ${\displaystyle r}$-uniform hypergraph with at most ${\displaystyle \delta n^{v(H)}}$ subgraphs isomorphic to ${\displaystyle H}$, then it is possible to eliminate all copies of ${\displaystyle H}$ from ${\displaystyle G}$ by removing at most ${\displaystyle \varepsilon n^{r}}$ hyperedges from ${\displaystyle G}$.

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

Proof idea of the hypergraph removal lemma

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). 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. ^[13] 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.

Proof idea for 3-uniform hypergraphs

For example, we demonstrate an informal 3-hypergraph version of Szemerédi's regularity lemma, first given by Frankl and Rödl. ^[14] 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

${\displaystyle \left|d\left(G_{i}^{(2)},G_{j}^{(2)},G_{k}^{(2)}\right)-d\left(A_{i}^{(2)},A_{j}^{(2)},A_{k}^{(2)}\right)\right|\leq \varepsilon ,}$

where ${\displaystyle d(X,Y,Z)}$ denotes the proportion of ${\displaystyle 3}$-uniform hyperedge in ${\displaystyle G^{(3)}}$ among all triangles on top of ${\displaystyle (X,Y,Z)}$.

We then subsequently define a regular partition as a partition in which the triples of parts that are not regular constitute at most an ${\displaystyle \varepsilon }$ fraction of all triples of parts in the partition.

In addition to this, we need to further regularize ${\displaystyle G_{1}^{(2)},\dots ,G_{l}^{(2)}}$ via a partition of the vertex set. As a result, we have the total data of hypergraph regularity as follows:

1. a partition of ${\displaystyle E(K_{n})}$ into graphs such that ${\displaystyle G^{(3)}}$ sits pseudorandomly on top;
2. a partition of ${\displaystyle V(G)}$ such that the graphs in (1) are extremely pseudorandom (in a fashion resembling Szemerédi's regularity lemma).

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 ${\displaystyle r_{k}(N)}$ be the size of the largest subset of ${\displaystyle \{1,\ldots ,N\}}$ that does not contain a length ${\displaystyle k}$ arithmetic progression. Szemerédi's theorem states that, ${\displaystyle r_{k}(N)=o(N)}$ for any constant ${\displaystyle k}$. The high level idea of the proof is that, we construct a hypergraph from a subset without any length ${\displaystyle k}$ 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 ${\displaystyle A\subset \{1,\ldots ,N\}}$ be a subset that does not contain any length ${\displaystyle k}$ arithmetic progression. Let ${\displaystyle M=k^{2}N+1}$ be a large enough integer. We can think of ${\displaystyle A}$ as a subset of ${\displaystyle \mathbb {Z} /M\mathbb {Z} }$. Clearly, if ${\displaystyle A}$ doesn't have length ${\displaystyle k}$ arithmetic progression in ${\displaystyle \mathbb {Z} }$, it also doesn't have length ${\displaystyle k}$ arithmetic progression in ${\displaystyle \mathbb {Z} /M\mathbb {Z} }$.

We will construct a ${\displaystyle k}$-partite ${\displaystyle (k-1)}$-uniform hypergraph ${\displaystyle G}$ from ${\displaystyle A}$ with parts ${\displaystyle V_{1},V_{2},\ldots ,V_{k}}$, all of which are ${\displaystyle M}$ element vertex sets indexed by ${\displaystyle \mathbb {Z} /M\mathbb {Z} }$. For each ${\displaystyle 1\leq i\leq k}$, we add a hyperedge among vertices ${\displaystyle (v_{j}\in V_{j})_{j\in [k]\setminus \{i\}}}$ if and only if ${\displaystyle \sum _{j\neq i}(j-i)v_{j}\in A.}$ Let ${\displaystyle H}$ be the complete ${\displaystyle k}$-partite ${\displaystyle (k-1)}$-uniform hypergraph. If ${\displaystyle G}$contains an isomorphic copy of ${\displaystyle H}$ with vertices ${\displaystyle v_{1},\ldots ,v_{k}}$, then ${\displaystyle \alpha _{i}=\sum _{j\neq i}(j-i)v_{j}\in A}$ for any ${\displaystyle 1\leq i\leq j}$. However, note that ${\displaystyle \alpha _{i}}$ is a length ${\displaystyle k}$ arithmetic progression with common difference ${\displaystyle \alpha _{i+1}-\alpha _{i}=-\sum _{j}v_{j}}$. Since ${\displaystyle A}$ has no length ${\displaystyle k}$ arithmetic progression, it must be the case that ${\displaystyle \alpha _{1}=\cdots =\alpha _{k}}$, so ${\displaystyle \sum _{j}v_{j}=0}$.

Thus, for each hyperedge ${\displaystyle (v_{j}\in V_{j})_{j\in [k]\setminus \{i\}}}$, we can find a unique copy of ${\displaystyle H}$ that this edge lies in by finding ${\displaystyle v_{i}=-\sum _{j\neq i}v_{j}}$. The number of copies of ${\displaystyle H}$ in ${\displaystyle G}$ equals ${\displaystyle {\frac {1}{k}}e(G)=O(N^{k-1})=o(N^{k})}$. Therefore, by the hypergraph removal lemma, we can remove ${\displaystyle o(N^{k-1})}$ edges to eliminate all copies of ${\displaystyle H}$ in ${\displaystyle G}$. Since every hyperedge of ${\displaystyle G}$ is in a unique copy of ${\displaystyle H}$, to eliminate all copies of ${\displaystyle H}$ in ${\displaystyle G}$, we need to remove at least ${\displaystyle e(G)/k}$ edges. Thus, ${\displaystyle e(G)=o(N^{k-1})}$.

The number of hyperedges in ${\displaystyle G}$ is ${\displaystyle kM^{k-2}|A|=o(N^{k-1})}$, which concludes that ${\displaystyle |A|=o(N)}$.

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 ${\displaystyle |A|\leq {\frac {N}{(\log \log N)^{c_{k}}}}}$ for some constant ${\displaystyle c_{k}}$ depending on ${\displaystyle k}$. ^[15] It is the best bound for ${\displaystyle k\geq 5}$ so far.

Applications

• The hypergraph removal lemma is used to prove the multidimensional Szemerédi theorem by J. Solymosi. ^[16] The statement is that any for any finite subset ${\displaystyle S}$ of ${\displaystyle \mathbb {Z} ^{r}}$, any ${\displaystyle \delta >0}$ and any ${\displaystyle n}$ large enough, any subset of ${\displaystyle [n]^{r}}$ of size at least ${\displaystyle \delta n^{r}}$ contains a subset of the form ${\displaystyle a\cdot S+d}$, that is, a dilated and translated copy of ${\displaystyle S}$. Corners theorem is a special case when ${\displaystyle S=\{(0,0),(0,1),(1,0)\}}$.
• 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. ^{[17] [18]}

See also

• Graph removal lemma
• Szemerédi's theorem
• Problems involving arithmetic progressions

References

1. Rodl, V.; Nagle, B.; Skokan, J.; Schacht, M.; Kohayakawa, Y. (2005-05-26). "From The Cover: The hypergraph regularity method and its applications". Proceedings of the National Academy of Sciences. 102 (23): 8109–8113. Bibcode:2005PNAS..102.8109R. doi: 10.1073/pnas.0502771102 . ISSN   0027-8424. PMC   1149431 . PMID   15919821.
2. Gowers, William (2007-11-01). "Hypergraph regularity and the multidimensional Szemerédi theorem". Annals of Mathematics. 166 (3): 897–946. arXiv: 0710.3032 . Bibcode:2007arXiv0710.3032G. doi:10.4007/annals.2007.166.897. ISSN   0003-486X.
3. Haviland, Julie; Thomason, Andrew (May 1989). "Pseudo-random hypergraphs". Discrete Mathematics. 75 (1–3): 255–278. doi: 10.1016/0012-365x(89)90093-9 . ISSN   0012-365X.
4. Chung, F. R. K.; Graham, R. L. (1989-11-01). "Quasi-random hypergraphs". Proceedings of the National Academy of Sciences. 86 (21): 8175–8177. Bibcode:1989PNAS...86.8175C. doi: 10.1073/pnas.86.21.8175 . ISSN   0027-8424. PMC   298241 . PMID   16594074.
5. Chung, Fan R. K. (1990). "Quasi-random classes of hypergraphs". Random Structures and Algorithms. 1 (4): 363–382. doi:10.1002/rsa.3240010401. ISSN   1042-9832.
6. Chung, F. R. K.; Graham, R. L. (1990). "Quasi-random hypergraphs". Random Structures and Algorithms. 1 (1): 105–124. doi:10.1002/rsa.3240010108. ISSN   1042-9832. PMC   298241 . PMID   16594074.
7. Chung, F. R. K.; Graham, R. L. (January 1991). "Quasi-Random Set Systems". Journal of the American Mathematical Society. 4 (1): 151. doi: 10.2307/2939258 . ISSN   0894-0347. JSTOR   2939258.
8. Kohayakawa, Yoshiharu; Rödl, Vojtěch; Skokan, Jozef (February 2002). "Hypergraphs, Quasi-randomness, and Conditions for Regularity". Journal of Combinatorial Theory, Series A. 97 (2): 307–352. doi: 10.1006/jcta.2001.3217 . ISSN   0097-3165.
9. Frieze, Alan; Kannan, Ravi (1999-02-01). "Quick Approximation to Matrices and Applications". Combinatorica. 19 (2): 175–220. doi:10.1007/s004930050052. ISSN   0209-9683.
10. Czygrinow, Andrzej; Rödl, Vojtech (January 2000). "An Algorithmic Regularity Lemma for Hypergraphs". SIAM Journal on Computing. 30 (4): 1041–1066. doi:10.1137/s0097539799351729. ISSN   0097-5397.
11. Chung, Fan R.K. (2007-07-05). "Regularity lemmas for hypergraphs and quasi-randomness". Random Structures & Algorithms. 2 (2): 241–252. doi:10.1002/rsa.3240020208. ISSN   1042-9832.
12. Frankl, P.; Rödl, V. (December 1992). "The Uniformity Lemma for hypergraphs". Graphs and Combinatorics. 8 (4): 309–312. doi:10.1007/bf02351586. ISSN   0911-0119.
13. Nagle, Brendan; Rödl, Vojtěch (2003-07-17). "Regularity properties for triple systems". Random Structures & Algorithms. 23 (3): 264–332. doi:10.1002/rsa.10094. ISSN   1042-9832.
14. Frankl, Peter; Rödl, Vojtěch (2002-02-07). "Extremal problems on set systems". Random Structures & Algorithms. 20 (2): 131–164. doi:10.1002/rsa.10017. ISSN   1042-9832.
15. Gowers, W. T. (1998-07-01). "A New Proof of Szemerédi's Theorem for Arithmetic Progressions of Length Four". Geometric and Functional Analysis. 8 (3): 529–551. doi:10.1007/s000390050065. ISSN   1016-443X.
16. SOLYMOSI, J. (March 2004). "A Note on a Question of Erdős and Graham". Combinatorics, Probability and Computing. 13 (2): 263–267. doi:10.1017/s0963548303005959. ISSN   0963-5483.
17. Bergelson, Vitaly; Leibman, Alexander; Ziegler, Tamar (February 2011). "The shifted primes and the multidimensional Szemerédi and polynomial Van der Waerden theorems". Comptes Rendus Mathématique. 349 (3–4): 123–125. arXiv: 1007.1839 . doi:10.1016/j.crma.2010.11.028. ISSN   1631-073X.
18. Furstenberg, H.; Katznelson, Y. (December 1991). "A density version of the Hales-Jewett theorem". Journal d'Analyse Mathématique. 57 (1): 64–119. doi:10.1007/bf03041066. ISSN   0021-7670.