hypergraph removal lemma

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

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

Graph removal lemma is a special case with $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{{Cite journal|last1=Haviland|first1=Julie|last2=Thomason|first2=Andrew|date=May 1989|title=Pseudo-random hypergraphs|journal=Discrete Mathematics|volume=75|issue=1–3|pages=255–278|doi=10.1016/0012-365x(89)90093-9|issn=0012-365X|doi-access=free}}{{Cite journal|last1=Chung|first1=F. R. K.|last2=Graham|first2=R. L.|date=1989-11-01|title=Quasi-random hypergraphs|journal=Proceedings of the National Academy of Sciences|volume=86|issue=21|pages=8175–8177|bibcode=1989PNAS...86.8175C|doi=10.1073/pnas.86.21.8175|issn=0027-8424|pmc=298241|pmid=16594074|doi-access=free}}{{Cite journal|last=Chung|first=Fan R. K.|date=1990|title=Quasi-random classes of hypergraphs|journal=Random Structures and Algorithms|volume=1|issue=4|pages=363–382|doi=10.1002/rsa.3240010401|issn=1042-9832}}{{Cite journal|last1=Chung|first1=F. R. K.|last2=Graham|first2=R. L.|date=1990|title=Quasi-random hypergraphs|journal=Random Structures and Algorithms|volume=1|issue=1|pages=105–124|doi=10.1002/rsa.3240010108|issn=1042-9832|pmc=298241|pmid=16594074}}{{Cite journal|last1=Chung|first1=F. R. K.|last2=Graham|first2=R. L.|date=January 1991|title=Quasi-Random Set Systems|journal=Journal of the American Mathematical Society|volume=4|issue=1|pages=151|doi=10.2307/2939258|issn=0894-0347|jstor=2939258|doi-access=free}}{{Cite journal|last1=Kohayakawa|first1=Yoshiharu|last2=Rödl|first2=Vojtěch|last3=Skokan|first3=Jozef|date=February 2002|title=Hypergraphs, Quasi-randomness, and Conditions for Regularity|journal=Journal of Combinatorial Theory | series=Series A|volume=97|issue=2|pages=307–352|doi=10.1006/jcta.2001.3217|issn=0097-3165|doi-access=free}}{{Cite journal|last1=Frieze|first1=Alan|last2=Kannan|first2=Ravi|date=1999-02-01|title=Quick Approximation to Matrices and Applications|journal=Combinatorica|volume=19|issue=2|pages=175–220|doi=10.1007/s004930050052|issn=0209-9683}}{{Cite journal|last1=Czygrinow|first1=Andrzej|last2=Rödl|first2=Vojtech|date=January 2000|title=An Algorithmic Regularity Lemma for Hypergraphs|journal=SIAM Journal on Computing|volume=30|issue=4|pages=1041–1066|doi=10.1137/s0097539799351729|issn=0097-5397}}{{Cite journal|last=Chung|first=Fan R.K.|date=2007-07-05|title=Regularity lemmas for hypergraphs and quasi-randomness|journal=Random Structures & Algorithms|volume=2|issue=2|pages=241–252|doi=10.1002/rsa.3240020208|issn=1042-9832}}{{Cite journal|last1=Frankl|first1=P.|last2=Rödl|first2=V.|date=December 1992|title=The Uniformity Lemma for hypergraphs|journal=Graphs and Combinatorics|volume=8|issue=4|pages=309–312|doi=10.1007/bf02351586|issn=0911-0119}} 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 $k>2$, if we simply regulate $k$-hyperedges using only 1-hyperedge, we will lose information of all $j$-hyperedges in the middle where

For example, we demonstrate an informal 3-hypergraph version of Szemerédi's regularity lemma, first given by Frankl and Rödl.{{Cite journal|last1=Frankl|first1=Peter|last2=Rödl|first2=Vojtěch|date=2002-02-07|title=Extremal problems on set systems|journal=Random Structures & Algorithms|volume=20|issue=2|pages=131–164|doi=10.1002/rsa.10017|issn=1042-9832}} Consider a partition of edges$E(K\_n)\; =\; G^\{(2)\}\_1\backslash cup\backslash dots\backslash cup\; G^\{(2)\}\_l$ such that for most triples $(i,j,k),$ there are a lot of triangles on top of $\backslash left(G^\{(2)\}\_i,G^\{(2)\}\_j,G^\{(2)\}\_k\backslash right).$ We say that $\backslash left(G^\{(2)\}\_i,G^\{(2)\}\_j,G^\{(2)\}\_k\backslash right)$ is "pseudorandom" in the sense that for all subgraphs $A^\{(2)\}\_i\backslash subset\; G^\{(2)\}\_i$ with not too few triangles on top of $\backslash left(A^\{(2)\}\_i,A^\{(2)\}\_j,A^\{(2)\}\_k\backslash right),$ we have

:$$

\left|d\left(G^{(2)}_i,G^{(2)}_j,G^{(2)}_k\right) - d\left(A^{(2)}_i,A^{(2)}_j,A^{(2)}_k\right)\right|\le\varepsilon,

:where $d(X,\; Y,\; Z)$ denotes the proportion of $3$-uniform hyperedge in $G^\{(3)\}$ among all triangles on top of $(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 $\backslash varepsilon$ fraction of all triples of parts in the partition.

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

1. a partition of $E(K\_n)$ into graphs such that $G^\{(3)\}$ sits pseudorandomly on top;
2. a partition of $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.

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

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

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

The number of hyperedges in $G$ is $kM^\{k-2\}|A|\; =\; o(N^\{k-1\})$, which concludes that $|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, Leng, Sah, and Sawhney proved that $|A|\; \backslash le\; \backslash frac\{N\}\{\backslash exp(-(\backslash log\; \backslash log\; N)^\{c\_k\})\}$ for some constant $c\_k$ depending on $k$.{{Cite arXiv |eprint=2402.17995 |first1=James |last1=Leng |first2=Ashwin |last2=Sah |title=Improved Bounds for Szemerédi's Theorem |date=2024 |last3=Sawhney |first3=Mehtaab}} It is the best bound for $k\; \backslash ge\; 5$ so far.

• The hypergraph removal lemma is used to prove the multidimensional Szemerédi theorem by J. Solymosi.{{Cite journal|last=SOLYMOSI|first=J.|date=March 2004|title=A Note on a Question of Erdős and Graham|journal=Combinatorics, Probability and Computing|volume=13|issue=2|pages=263–267|doi=10.1017/s0963548303005959|issn=0963-5483}} The statement is that any for any finite subset $S$ of $\backslash mathbb\{Z\}^r$, any $\backslash delta>0$ and any $n$ large enough, any subset of $[n]^r$ of size at least $\backslash delta\; n^r$ contains a subset of the form $a\backslash cdot\; S\; +\; d$, that is, a dilated and translated copy of $S$. Corners theorem is a special case when $S=\backslash \{(0,0),(0,1),(1,0)\backslash \}$.
• 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.{{Cite journal|last1=Bergelson|first1=Vitaly|last2=Leibman|first2=Alexander|last3=Ziegler|first3=Tamar|date=February 2011|title=The shifted primes and the multidimensional Szemerédi and polynomial Van der Waerden theorems|journal=Comptes Rendus Mathématique|volume=349|issue=3–4|pages=123–125|doi=10.1016/j.crma.2010.11.028|issn=1631-073X|arxiv=1007.1839}}{{Cite journal|last1=Furstenberg|first1=H.|last2=Katznelson|first2=Y.|date=December 1991|title=A density version of the Hales-Jewett theorem|journal=Journal d'Analyse Mathématique|volume=57|issue=1|pages=64–119|doi=10.1007/bf03041066|doi-access=free|issn=0021-7670}}

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

{{reflist}}

Category:Hypergraphs

Category:Theorems in graph theory