Content deleted Content added
No edit summary |
|||
Line 52:
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.
This theorem roughly implies that any dense subset of <math> \mathbb{Z}^d </math> contains any finite pattern of <math> \mathbb{Z}^d </math>. The case when <math> d = 1 </math> and the pattern is arithmetic progression of length some length is equivalent to Szemerédi's theorem.<blockquote>
==== Furstenberg and Katznelson Theorem<ref name=":0" /> ====
Let <math> T </math> be a finite subset of <math> \mathbb{R}^d </math> and let <math> \delta > 0 </math> be given. Then there exists a finite subset <math> C \subset \mathbb{R}^d </math> such that all <math> Z \subset C </math> with <math> |Z| > \delta |C| </math> contains a homothetic copy of <math> T </math>. (i.e. set of form <math> z + \lambda T </math>, for some <math> z \in \mathbb{R}^d </math> and <math> t \in \mathbb{R} </math>)
| |||