Hypergraph regularity method: Difference between revisions

Revision as of 00:21, 28 November 2021

Revision as of 00:24, 28 November 2021

Line 77:

== Applications ==

The main application through which most others follow is the hypergraph removal lemma, which roughly states that given fixed <math> \mathcal{F}^{(k)} </math> and large <math> \mathcal{H}^{(k)} </math> <math> k </math>-uniform hypergraphs, if <math> \mathcal{H}^{(k)} </math> contains few copies of <math> \mathcal{F}^{(k)} </math>, then one can delete few hyperedges in <math> \mathcal{H}^{(k)} </math> to eliminate all of the copies of <math> \mathcal{F}^{(k)} </math>. To state it more formally,

\begin{theorem}[=== 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.

\end{theorem}

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 88:

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.

\begin{theorem}[==== Furstenberg and Katznelson] Theorem ====

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>.

\end{theorem}

Another possible generalization is when it is allowed the dimension to grow.

\begin{theorem}[==== Tengan, Tokushige, V.R., and M.S] Theorem ====

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.

\end{theorem}