Hypergraph regularity method: Difference between revisions

Revision as of 23:50, 27 November 2021

Revision as of 23:53, 27 November 2021

Line 1:

{{AfC submission|t||ts=20211127234938|u=Lepsvera|ns=118|demo=}}<!-- Important, do not remove this line before article has been created. -->

Line 8 ⟶ 10:

Very informally, hypergraph regularity lemma decomposes any given <nowiki><math> k <\/math></nowiki>-uniform hypergraph into random-like object with bounded parts (with an appropriate boundedness and randomness notions) that is usually easier to work with.</nowiki>

On the other hand, hypergraph counting lemma estimates the number of hypergraphs of given isomorphism class in some collections of the random-like parts.

This is an extension of Szemerédi's regularity lemma that decomposes any given graph into pseudorandom blocks, namely <nowiki><math> \varepsilon <\/math></nowiki>-regular pairs, and graph counting lemma that estimates number of copies of a fixed graph as a subgraph of a larger graph.</nowiki>

Line 31 ⟶ 33:

\begin{itemize}

   \item <nowiki><math> K_j^{(k)} <\/math></nowiki> denotes a <nowiki><math> k <\/math></nowiki>-uniform clique on <nowiki><math> j <\/math> vertices</nowiki> vertices

   \item <nowiki><math> \mathcal{G}^{(j)} <\/math></nowiki> is an <nowiki><math> l <\/math></nowiki>-partite <nowiki><math> j <\/math></nowiki>-graph on vertex partition <nowiki><math> \mathcal{G}^{(1)} = V_1 \sqcup \ldots \sqcup V_l <\/math></nowiki>

   \item <nowiki><math> \mathcal{K}_j(\mathcal{G}^{(i)}) <\/math></nowiki> is the family of all <nowiki><math> j <\/math></nowiki>-element vertex sets that span the clique <nowiki><math> K_j^{(i)} <\/math></nowiki> in <nowiki><math> \mathcal{G}^{(i)} <\/math></nowiki>. In particular, <nowiki><math> \mathcal{K}_j(\mathcal{G}^{(1)}) = K_l^{(j)}(V_1, \ldots, V_l) <\/math></nowiki>, a complete <nowiki><math> l <\/math></nowiki>-partite <nowiki><math> j <\/math>-graph.</nowiki>-graph.

\end{itemize}

Line 44 ⟶ 46:

\begin{definition}[Relative density]

For <nowiki><math> j \geq 3 <\/math></nowiki>, fix some classes <nowiki><math> V_{i_1}, \ldots, V_{i_j} <\/math></nowiki> of <nowiki><math> \mathcal{G}^{(1)} <\/math></nowiki> with <nowiki><math> 1 \leq i_1 < \ldots < i_j \leq l <\/math></nowiki>. Suppose <nowiki><math> r \geq 1 <\/math></nowiki> is an integer. Let <nowiki><math> \mathbf{Q}^{(j-1)} = \{ Q_1^{(j-1)}, \ldots, Q_r^{(j-1)} \} <\/math></nowiki> be a subhypergraph of the induced <nowiki><math> j <\/math></nowiki>-partite  graph <nowiki><math> \mathcal{G}^{(j-1)}[V_{i_1}, \ldots, V_{i_j}] <\/math></nowiki>. Define the relative density</nowiki>

\begin{equation*}

Line 55 ⟶ 57:

The following is the appropriate notion of pseudorandomness that the regularity method will use. Informally, by this concept of regularity, <nowiki><math> j-1 <\/math></nowiki>-edges (<nowiki><math> \mathcal{G}^{(j-1)} <\/math></nowiki>) have some control over <nowiki><math> j <\/math></nowiki>-edges (<nowiki><math> \mathcal{G}^{(j)} <\/math>).</nowiki>).

\begin{definition}[(<nowiki>[(<math> \delta_j, d_j, r <\/math>)-regularity]</nowiki>

Suppose <nowiki><math> \delta_j, d_j <\/math></nowiki> are positive real numbers and <nowiki><math> r \geq 1 <\/math></nowiki> is an integer. <nowiki><math> \mathcal{G}^{(j)} <\/math></nowiki> is (<nowiki><math> \delta_j, d_j, r <\/math></nowiki>)-regular with respect to <nowiki><math> \mathcal{G}^{(j-1)} <\/math></nowiki> if for any choice of classes <nowiki><math> V_{i_1}, \ldots, V_{i_j} <\/math></nowiki> and any collection of subhypergraphs <nowiki><math> \mathbf{Q}^{(j-1)} = \{ Q_1^{(j-1)}, \ldots, Q_r^{(j-1)} \} <\/math></nowiki> of <nowiki><math> \mathcal{G}^{(j-1)}[V_{i_1}, \ldots, V_{i_j}] <\/math> satisfying</nowiki> satisfying

\begin{equation*}

Line 68 ⟶ 70:

\end{equation*}

we have <nowiki><math>  d(\mathcal{G}^{(j)} \vert \mathbf{Q}^{(j-1)}) = d_j \pm \delta_j <\/math></nowiki>

\end{definition}

Roughly speaking, following describes the pseudorandom blocks into which the hypergraph regularity lemma decomposes any large enough hypergraph. In Szemerédi regularity 2-edges are regularized versus 1-edges (vertices). In this generalized notion, <nowiki><math> j <\/math></nowiki>-edges are regularized versus <nowiki><math> (j-1) <\/math></nowiki>-edges, for all <nowiki><math> 2\leq j\leq h <\/math>.</nowiki>.

\begin{definition}[<nowiki>[<math> (\delta, \mathbf{d},r) <\/math>-regular <math> (l, h) <\/math>-complex]</nowiki>

An <nowiki><math> (l,h) <\/math></nowiki>-complex <nowiki><math> \mathbf{G} <\/math></nowiki> is a system <nowiki><math> \{\mathcal{G}^{(j)}\}_{j=1}^h <\/math></nowiki> of <nowiki><math> l <\/math></nowiki>-partite <nowiki><math> j <\/math></nowiki> graphs <nowiki><math> \mathcal{G}^{(j)} <\/math></nowiki> satisfying <nowiki><math> \mathcal{G}^{(j)} \subset \mathcal{K}_j(\mathcal{G}^{(j-1)}) <\/math></nowiki>. Given vectors of positive real numbers <nowiki><math> \delta = (\delta_2, \ldots, \delta_h) <\/math></nowiki>, <nowiki><math> \mathbf{d} = (d_2, \ldots, d_h) <\/math></nowiki>, and an integer <nowiki><math> r \geq 1 <\/math></nowiki>, we say <nowiki><math> (l, h) <\/math></nowiki>-complex is <nowiki><math> (\delta, \mathbf{d},r) <\/math>-regular if</nowiki>-regular if

\begin{enumerate}

   \item For each <nowiki><math> 1 \leq i_1 < i_2 \leq l <\/math></nowiki>, <nowiki><math> \mathcal{G}^{(2)}[V_{i_1},V_{i_2}] <\/math></nowiki> is <nowiki><math> \delta_2 <\/math></nowiki>-regular with density <nowiki><math> d_2 \pm \delta_2 <\/math>.</nowiki>.

   \item For each <nowiki><math> 3 \leq j \leq h <\/math></nowiki>, <nowiki><math> \mathcal{G}^{(j)} <\/math></nowiki> is (<nowiki><math> \delta_j, d_j, r <\/math></nowiki>)-regular with respect to <nowiki><math> \mathcal{G}^{(j-1)} <\/math></nowiki>

\end{enumerate}

Line 91 ⟶ 93:

The following describes the equitable partition that the hypergraph regularity lemma will induce. The <nowiki><math> (\mu, \delta, \mathbf{d}, r) <\/math></nowiki>-equitable family of partition is a sequence of partitions of 1-edges (vertices), 2-edges (pairs), 3-edges (triples), etc.</nowiki>

\begin{definition}[<nowiki>[<math> (\mu, \delta, \mathbf{d}, r) <\/math>-equitable partition]</nowiki>

Let <nowiki><math> \mu > 0 <\/math></nowiki> be a real number, <nowiki><math> r \geq 1 <\/math></nowiki> be an integer, and <nowiki><math> \delta = (\delta_2, \ldots, \delta_{k-1}) <\/math></nowiki>, <nowiki><math> \mathbf{d}=(d_2, \ldots, d_{k-1}) <\/math></nowiki> be vectors of positive reals. Let <nowiki><math> \mathbf{a} = (a_1, \ldots, a_{k-1}) <\/math></nowiki> be a vector of positive integers and <nowiki><math> V <\/math></nowiki> be an <nowiki><math> n <\/math></nowiki>-element vertex set. We say that a family of partitions <nowiki><math> \mathcal{P} = \mathcal{P}(k-1, \mathbf{a}) = \{\mathcal{P}^{(1)}\, \ldots, \mathcal{P}^{(k-1)}\} <\/math></nowiki> on <nowiki><math> V <\/math></nowiki> is <nowiki><math> (\mu, \delta, \mathbf{d}, r) <\/math></nowiki>-equitable if it satisfies the following</nowiki>

\begin{enumerate}

   \item <nowiki><math> \mathcal{P}^{(1)} = \{V_i \colon i \in [a_1]\} <\/math></nowiki> is equitable vertex partition of <nowiki><math> V <\/math></nowiki>. That is <nowiki><math> |V_1| \leq \ldots \leq |V_{a_1}| \leq | V_1| + 1 <\/math></nowiki>

   \item <nowiki><math> \mathcal{P}^{(j)} <\/math></nowiki> partitions <nowiki><math> \mathcal{K}_j(\mathcal{G}^{(1)}) = K_{a_1}^{(j)}(V_1, \ldots, V_{a_1}) <\/math></nowiki> so that if <nowiki><math> P_1^{(j-1)}, \ldots, P_j^{(j-1)} \in \mathcal{P}^{(j-1)} <\/math> and</nowiki> and

   <nowiki><math> \mathcal{K}_j(\cup_{i=1}^jP_i{(j-1)}) \neq \emptyset <\/math></nowiki>  then <nowiki><math> \mathcal{K}_j(\cup_{i=1}^jP_i{(j-1)}) <\/math></nowiki> is partitioned into at most <nowiki><math> a_j <\/math></nowiki> parts, all of which are members <nowiki><math> \mathcal{P}^{(j)} <\/math></nowiki>

   \item For all but at most <nowiki><math> \mu n^k <\/math></nowiki>  <nowiki><math> k <\/math></nowiki>-tuples <nowiki><math> K \in \binom{V}{k} <\/math></nowiki> there is unique <nowiki><math> (\delta, \mathbf{d},r) <\/math></nowiki>-regular <nowiki><math> (k, k-1) <\/math></nowiki>-complex <nowiki><math> \mathbf{P} = \{P^{(j)}\}_{j=1}^{k-1} <\/math></nowiki> such that <nowiki><math> P^{(j)} <\/math></nowiki> has as members <nowiki><math> \binom{k}{j} <\/math></nowiki> different partition classes from <nowiki><math> \mathcal{P}^{(j)} <\/math></nowiki> and <nowiki><math> K \in \mathcal{K}_k(P^{(k-1)}) \subset \ldots \subset \mathcal{K}_k(P^{(1)}) <\/math></nowiki>

\end{enumerate}

Line 116 ⟶ 118:

\begin{definition}

We say that a <nowiki><math> k <\/math></nowiki>-graph <nowiki><math> \mathcal{H}^{(k)} <\/math></nowiki> is <nowiki><math> (\delta_k, r) <\/math></nowiki>-regular with respect to a family of partitions <nowiki><math> \mathcal{P} <\/math></nowiki> if all but at most <nowiki><math> \delta_k n^k <\/math></nowiki>  <nowiki><math> k- <\/math>edges</nowiki>edges

<nowiki><math> K <\/math></nowiki> of <nowiki><math> \mathcal{H}^{(k)} <\/math></nowiki> have the property that <nowiki><math> K \in \mathcal{K}_k(\mathcal{G}^{(1)}) <\/math></nowiki> and if <nowiki><math> \mathbf{P} = \{P^{(j)}\}_{j=1}^{k-1} <\/math></nowiki> is unique <nowiki><math> (k, k-1) <\/math></nowiki>-complex for which <nowiki><math> K \in \mathcal{K}_k(P^{(k-1)}) <\/math></nowiki>, then <nowiki><math> \mathcal{H}^{(k)} <\/math></nowiki> is <nowiki><math> (\delta_k, d(\mathcal{H}^{(k)} \vert P^{(k-1)}), r)  <\/math></nowiki> regular with respect to <nowiki><math> \mathcal{P} <\/math>.</nowiki>.

Line 127 ⟶ 129:

\begin{theorem}[Hypergraph regularity lemma]

For all positive real <nowiki><math> \mu <\/math></nowiki>, <nowiki><math> \delta_k <\/math>, functions</nowiki>, functions

\begin{equation*}

Line 135 ⟶ 137:

\end{equation*}

for <nowiki><math> j = 2, \ldots, k-1 <\/math></nowiki>, and <nowiki><math> r \colon \mathbb{N} \times (0, 1]^{k-2} \to \mathbb{N} <\/math>,</nowiki>,

there exists <nowiki><math> T_0 <\/math></nowiki> and <nowiki><math> n_0 <\/math></nowiki> so that the following holds. For any <nowiki><math> k <\/math></nowiki>-uniform hypergraph <nowiki><math> \mathcal{H}^{(k)} <\/math></nowiki> on <nowiki><math> n \geq n_0 <\/math></nowiki> vertices, there exists a family of partitions <nowiki><math> \mathcal{P} = \mathcal{P}(k-1, \mathbf{a}) <\/math></nowiki> and a vector <nowiki><math> \mathbf{d} = (d_2, \ldots, d_{k-1}) <\/math></nowiki> so that, for <nowiki><math> \mathbf{\delta} = (\delta_2, \ldots, \delta_{k-1}) <\/math></nowiki> where <nowiki><math> \delta_j = \delta_j(d_j, \ldots, d_{k-1}) <\/math></nowiki> for all <nowiki><math> j <\/math></nowiki>, and <nowiki><math> r = r(a_1, \mathbf{d}) <\/math></nowiki>, the following holds</nowiki>

\begin{enumerate}

   \item <nowiki><math> \mathcal{P} <\/math></nowiki> is a <nowiki><math> (\mu, \mathbf{\delta}, \mathbf{d}, r) <\/math></nowiki>-equitable family of partitions and <nowiki><math> a_i \leq T_0 <\/math></nowiki> for every <nowiki><math> i = 1, \ldots, k-1 <\/math></nowiki>

   \item <nowiki><math> \mathcal{H}^{(k)} <\/math></nowiki> is <nowiki><math> (\delta_k, r) <\/math></nowiki> regular with respect to <nowiki><math> \mathcal{P} <\/math></nowiki>

\end{enumerate}

Line 154 ⟶ 156:

\begin{theorem}[Hypergraph counting lemma]

For all integers <nowiki><math> 2 \leq k \leq l <\/math></nowiki> the following holds:</nowiki>

<nowiki><math> \forall \gamma > 0 \; \; \forall d_k > 0 \; \; \exists \delta_k > 0 \;\; \forall d_{k-1} > 0 \; \; \exists \delta_{k-1} > 0 \; \cdots \; \forall d_2 > 0 \; \; \exists \delta_2>0 <\/math></nowiki> and there are integers <nowiki><math> r <\/math></nowiki> and <nowiki><math> m_0 <\/math></nowiki> so that, with <nowiki><math> \mathbf{d} = (d_2, \ldots, d_k) <\/math></nowiki>, <nowiki><math> \delta = (\delta_2, \ldots, \delta_k) <\/math></nowiki>, and <nowiki><math> m \geq m_0 <\/math>,</nowiki>,

if <nowiki><math> \mathbf{G} = \{ \mathcal{G}^{(j)}\}_{j=1}^k <\/math></nowiki> is a <nowiki><math> (\delta, \mathbf{d}, r) <\/math></nowiki>-regular <nowiki><math> (l,k) <\/math></nowiki> complex with wertex partition <nowiki><math> \mathcal{G}^{(1)} = V_1 \cup \cdots \cup V_l <\/math></nowiki> and <nowiki><math> |V_i| = m <\/math>, then</nowiki>, then

\begin{equation*}

Line 175 ⟶ 177:

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

\begin{theorem}[Hypergraph removal lemma]

For all <nowiki><math> l \geq k \geq 2 <\/math></nowiki> and every <nowiki><math> \mu > 0 <\/math></nowiki>, there exists <nowiki><math> \zeta > 0 <\/math></nowiki> and <nowiki><math> n_0 > 0 <\/math></nowiki> so that the following holds. Suppose <nowiki><math> \mathcal{F}^{(k)} <\/math></nowiki> is a <nowiki><math> k <\/math></nowiki>-uniform hypergraph on <nowiki><math> l <\/math></nowiki> vertices and <nowiki><math> \mathcal{H}^{(k)} <\/math></nowiki> is that on <nowiki><math> n \geq n_0 <\/math></nowiki> vertices. If <nowiki><math> \mathcal{H}^{(k)} <\/math></nowiki> contains at most <nowiki><math> \zeta n  <\/math></nowiki> copies of <nowiki><math> \mathcal{F}^{(k)} <\/math></nowiki>, then one can delete <nowiki><math> \mu n^k <\/math></nowiki> hyperedges in <nowiki><math> \mathcal{H}^{(k)} <\/math></nowiki> to make it <nowiki><math> \mathcal{F}^{(k)} <\/math>-free.</nowiki>-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 <nowiki><math> \mathbb{Z} <\/math></nowiki> 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  <nowiki><math> \mathbb{Z} <\/math></nowiki> contains an arithmetic progression of length 3.</nowiki>

Line 191 ⟶ 193:

This theorem roughly implies that any dense subset of <nowiki><math> \ZZ^d <\/math></nowiki> contains any finite pattern of <nowiki><math> \ZZ^d <\/math></nowiki>. The case when <nowiki><math> d = 1 <\/math></nowiki> and the pattern is arithmetic progression of length some length is equivalent to Szemerédi's theorem.</nowiki>

\begin{theorem}[Furstenberg and Katznelson]

Let <nowiki><math> T <\/math></nowiki> be a finite subset of <nowiki><math> \mathbb{R}^d <\/math></nowiki> and let <nowiki><math> \delta > 0 <\/math></nowiki> be given. Then there exists a finite subset <nowiki><math> C \subset \mathbb{R}^d <\/math></nowiki> such that all <nowiki><math> Z \subset C <\/math></nowiki> with <nowiki><math> |Z| > \delta |C| <\/math></nowiki> contains a homothetic copy of <nowiki><math> T <\/math></nowiki>. (i.e. set of form <nowiki><math> z + \lambda T <\/math></nowiki>, for some <nowiki><math> z \in \mathbb{R}^d <\/math></nowiki> and <nowiki><math> t \in \mathbb{R} <\/math>)</nowiki>)

Moreover, if <nowiki><math> T \subset [-t; t]^d <\/math></nowiki> for some <nowiki><math> t \in \mathbb{N} <\/math></nowiki>, then there exists <nowiki><math> N_0 \in \mathbb{N} <\/math></nowiki> such that <nowiki><math> C = [-N,N]^d <\/math></nowiki> has this property for all <nowiki><math> N \geq N_0 <\/math>.</nowiki>.

\end{theorem}

Line 209 ⟶ 211:

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

Let <nowiki><math> A <\/math></nowiki> be a finite ring. For every <nowiki><math> \delta > 0 <\/math></nowiki>, there exists <nowiki><math> M_0 <\/math></nowiki> such that, for <nowiki><math> M \geq M_0 <\/math></nowiki>, any subset <nowiki><math> Z \subset A^M <\/math></nowiki> with <nowiki><math> |Z| > \delta |A^M| <\/math></nowiki> contains a coset of an isomorphic copy of <nowiki><math> A <\/math></nowiki> (as a left <nowiki><math> A <\/math>-module).</nowiki>-module).

In other words, there are some <nowiki><math> \mathbf{r}, \mathbf{u} \in A^M <\/math></nowiki> such that <nowiki><math> r + \varphi(A) \subset Z <\/math></nowiki>, where <nowiki><math> \varphi \colon A \to A^M <\/math></nowiki>, <nowiki><math> \varphi(a)=a \mathbf{u} <\/math></nowiki> is an injection.</nowiki>

\end{theorem}