hypergraph removal lemma
{{Short description|Theorem in graph theory}}
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{{Cite journal|last1=Rodl|first1=V.|last2=Nagle|first2=B.|last3=Skokan|first3=J.|last4=Schacht|first4=M.|last5=Kohayakawa|first5=Y.|date=2005-05-26|title=From The Cover: The hypergraph regularity method and its applications|journal=Proceedings of the National Academy of Sciences|volume=102|issue=23|pages=8109–8113|doi=10.1073/pnas.0502771102|pmid=15919821|pmc=1149431|issn=0027-8424|bibcode=2005PNAS..102.8109R|doi-access=free}} and, independently, by Gowers.{{Cite journal|last=Gowers|first=William|date=2007-11-01|title=Hypergraph regularity and the multidimensional Szemerédi theorem|journal=Annals of Mathematics|volume=166|issue=3|pages=897–946|doi=10.4007/annals.2007.166.897|issn=0003-486X|bibcode=2007arXiv0710.3032G|arxiv=0710.3032}}
The hypergraph removal lemma can be used to prove results such as Szemerédi's theorem and the multi-dimensional Szemerédi theorem.
Statement
Let be -uniform (every edge connects exactly r vertices) hypergraph with vertices. The hypergraph removal lemma states that for any exists such that for any -uniform, -vertices hypergraph with fewer than subhypergraphs isomorphic to it is possible to remove all copies of by removing at most edges.
An equivalent formulation is that, for any hypergraph with copies of , we can eliminate all copies of from by removing hyperedges.
Graph removal lemma is a special case with .
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{{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 , if we simply regulate -hyperedges using only 1-hyperedge, we will lose information of all -hyperedges in the middle where
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.{{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
:
\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
We then subsequently define a regular partition as a partition in which the triples of parts that are not regular constitute at most an
In addition to this, we need to further regularize
- a partition of
E(K_n) into graphs such thatG^{(3)} sits pseudorandomly on top; - 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.
Proof of Szemerédi's theorem
Let
Let
We will construct a
Thus, for each hyperedge
The number of hyperedges in
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
Applications
- 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\mathbb{Z}^r , any\delta>0 and anyn large enough, any subset of[n]^r of size at least\delta n^r contains a subset of the forma\cdot S + d , that is, a dilated and translated copy ofS . Corners theorem is a special case whenS=\{(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.{{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}}