Content deleted Content added
No edit summary |
No edit summary |
||
Line 46:
=== [[Hypergraph removal lemma]] ===
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.
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.
Line 58 ⟶ 56:
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>)
Moreover, if <math> T \subset [-t; t]^d </math> for some <math> t \in \mathbb{N} </math>, then there exists <math> N_0 \in \mathbb{N} </math> such that <math> C = [-N,N]^d </math> has this property for all <math> N \geq N_0 </math>.</blockquote>Another possible generalization that can be proven by the removal lemma is when it is allowed the dimension to grow.<blockquote>
==== Tengan, Tokushige,
Let <math> A </math> be a finite ring. For every <math> \delta > 0 </math>, there exists <math> M_0 </math> such that, for <math> M \geq M_0 </math>, any subset <math> Z \subset A^M </math> with <math> |Z| > \delta |A^M| </math> contains a coset of an isomorphic copy of <math> A </math> (as a left <math> A </math>-module).
In other words, there are some <math> \mathbf{r}, \mathbf{u} \in A^M </math> such that <math> r + \varphi(A) \subset Z </math>, where <math> \varphi \colon A \to A^M </math>, <math> \varphi(a)=a \mathbf{u} </math> is an injection.
</blockquote> == References ==
<!-- Inline citations added to your article will automatically display here. See en.wikipedia.org/wiki/WP:REFB for instructions on how to add citations. -->
| |||