Content deleted Content added
Line 43:
=== [[Hypergraph removal lemma]] ===
<blockquote>For all <math> l \geq k \geq 2 </math> and every <math> \mu > 0 </math>, there exists <math> \zeta > 0 </math> and <math> n_0 > 0 </math> so that the following holds. Suppose <math> \mathcal{F}^{(k)} </math> is a <math> k </math>-uniform hypergraph on <math> l </math> vertices and <math> \mathcal{H}^{(k)} </math> is that on <math> n \geq n_0 </math> vertices. If <math> \mathcal{H}^{(k)} </math> contains at most <math> \zeta n </math> copies of <math> \mathcal{F}^{(k)} </math>, then one can delete <math> \mu n^k </math> hyperedges in <math> \mathcal{H}^{(k)} </math> to make it <math> \mathcal{F}^{(k)} </math>-free. </blockquote>One of the original motivations for graph regularity method was to prove a [[Szemerédi's theorem]], which states that every dense subset of <math> \mathbb{Z} </math> contains an arithmetic progression of arbitrary length. In fact, by a relatively simple application of [[triangle removal lemma]], one can prove that every dense subset of <math> \mathbb{Z} </math> contains an arithmetic progression of length 3.
The hypergraph regularity method and hypergraph removal lemma can prove high-dimensional and ring analogues of density version of Szemerédi's theorems, originally proved by Furstenberg and Katznelson<ref name=":0">{{Cite journal|last=Furstenberg|first=Hillel|last2=Katznelson|first2=Yitzhak|date=1978|title=An ergodic Szemeredi theorem for commuting transformations|journal=J. Analyse Math.|volume=34|pages=275–291}}</ref>. In fact, this approach yields first quantitative bounds for the theorems.
| |||