|
\section{Intro}
Hypergraph regularity method is a powerful tool that refers to the combined application of hypergraph regularity lemma and associated counting lemma. It is a generalization of graph regularity method, which refers to the use of Szemerédi's regularity and counting lemmas.
Hypergraph regularity method is a powerful tool that refers to the combined application of hypergraph regularity lemma and associated counting lemma. It is a generalization of graph regularity method, which refers to the use of Szemerédi's regularity and counting lemmas.
<nowiki> </nowiki>
Very informally, hypergraph regularity lemma decomposes any given <nowiki><math>k<\math>-uniform hypergraph into random-like object with bounded parts (with an appropriate boundedness and randomness notions) that is usually easier to work with.
On the other hand, hypergraph counting lemma estimates the number of hypergraphs of given isomorphism class in some collections of the random-like parts.
Very informally, hypergraph regularity lemma decomposes any given <nowiki><math>k<\math>-uniform hypergraph into random-like object with bounded parts (with an appropriate boundedness and randomness notions) that is usually easier to work with.</nowiki>
This is an extension of Szemerédi's regularity lemma that decomposes any given graph into pseudorandom blocks, namely <math>\varepsilon<\math>-regular pairs, and graph counting lemma that estimates number of copies of a fixed graph as a subgraph of a larger graph.
On the other hand, hypergraph counting lemma estimates the number of hypergraphs of given isomorphism class in some collections of the random-like parts.
There are several distinct formulations of the method, all of which imply hypergraph removal lemma and a number of other powerful results, such as Szemerédi's theorem, as well as some of its multidimensional extensions.
This is an extension of Szemerédi's regularity lemma that decomposes any given graph into pseudorandom blocks, namely <nowiki><math>\varepsilon<\math>-regular pairs, and graph counting lemma that estimates number of copies of a fixed graph as a subgraph of a larger graph.</nowiki>
\section{Statements}
The following formulations are due to [insert names], for alternative versions see [insert names]. In order to state hypergraph regularity and counting lemmas formally, we need to define several rather technical terms to formalize appropriate notions of pseudo-randomness (random-likeness) and boundedness, as well as to describe the random-like blocks and partitions.
There are several distinct formulations of the method, all of which imply hypergraph removal lemma and a number of other powerful results, such as Szemerédi's theorem, as well as some of its multidimensional extensions.
\begin{notation}
For brevity, define
\section{Statements}
\begin{itemize}
\item <math>K_j^{(k)}<\math> denotes a <math>k<\math>-uniform clique on <math>j<\math> vertices
\item <math>\mathcal{G}^{(j)}<\math> is an <math>l<\math>-partite <math>j<\math>-graph on vertex partition <math>\mathcal{G}^{(1)} = V_1 \sqcup \ldots \sqcup V_l<\math>
The following formulations are due to [insert names], for alternative versions see [insert names]. In order to state hypergraph regularity and counting lemmas formally, we need to define several rather technical terms to formalize appropriate notions of pseudo-randomness (random-likeness) and boundedness, as well as to describe the random-like blocks and partitions.
\item <math>\mathcal{K}_j(\mathcal{G}^{(i)})<\math> is the family of all <math>j<\math>-element vertex sets that span the clique <math>K_j^{(i)}<\math> in <math>\mathcal{G}^{(i)}<\math>. In particular, <math>\mathcal{K}_j(\mathcal{G}^{(1)}) = K_l^{(j)}(V_1, \ldots, V_l)<\math>, a complete <math>l<\math>-partite <math>j<\math>-graph.
\end{itemize}
\end{notation}
\begin{notation}
\begin{definition}[Relative density]
For brevity, define
For <math>j \geq 3<\math>, fix some classes <math>V_{i_1}, \ldots, V_{i_j}<\math> of <math>\mathcal{G}^{(1)}<\math> with <math>1 \leq i_1 < \ldots < i_j \leq l<\math>. Suppose <math>r \geq 1<\math> is an integer. Let <math>\mathbf{Q}^{(j-1)} = \{ Q_1^{(j-1)}, \ldots, Q_r^{(j-1)} \}<\math> be a subhypergraph of the induced <math>j<\math>-partite graph <math>\mathcal{G}^{(j-1)}[V_{i_1}, \ldots, V_{i_j}]<\math>. Define the relative density
\begin{equation*}
\begin{itemize}
d(\mathcal{G}^{(j)} \vert \mathbf{Q}^{(j-1)}) = \frac{|\mathcal{G}^{(j)} \cap \cup_{s \in [r]} \mathcal{K}_j(Q_s^{j-1})|}{|\cup_{s \in [r]} \mathcal{K}_j(Q_s^{j-1})|}
\end{equation*}
\item <nowiki><math>K_j^{(k)}<\math> denotes a <math>k<\math>-uniform clique on <math>j<\math> vertices</nowiki>
\end{definition}
The following is the appropriate notion of pseudorandomness that the regularity method will use. Informally, by this concept of regularity,\item <mathnowiki>j-1<\math>-edges (<math>\mathcal{G}^{(j-1)}<\math>) haveis somean control over<math>l<\math>-partite <math>j<\math>-edgesgraph on vertex partition (<math>\mathcal{G}^{(j1)} = V_1 \sqcup \ldots \sqcup V_l<\math>).</nowiki>
\item <nowiki><math>\mathcal{K}_j(\mathcal{G}^{(i)})<\math> is the family of all <math>j<\math>-element vertex sets that span the clique <math>K_j^{(i)}<\math> in <math>\mathcal{G}^{(i)}<\math>. In particular, <math>\mathcal{K}_j(\mathcal{G}^{(1)}) = K_l^{(j)}(V_1, \ldots, V_l)<\math>, a complete <math>l<\math>-partite <math>j<\math>-graph.</nowiki>
\begin{definition}[(<math>\delta_j, d_j, r<\math>)-regularity]
Suppose <math>\delta_j, d_j<\math> are positive real numbers and <math>r \geq 1<\math> is an integer. <math>\mathcal{G}^{(j)}<\math> is (<math>\delta_j, d_j, r<\math>)-regular with respect to <math>\mathcal{G}^{(j-1)}<\math> if for any choice of classes <math>V_{i_1}, \ldots, V_{i_j}<\math> and any collection of subhypergraphs <math>\mathbf{Q}^{(j-1)} = \{ Q_1^{(j-1)}, \ldots, Q_r^{(j-1)} \}<\math> of <math>\mathcal{G}^{(j-1)}[V_{i_1}, \ldots, V_{i_j}]<\math> satisfying
\end{itemize}
\begin{equation*}
|\cup_{s \in [r]}\mathcal{K}_j(Q_s)^{(j-1)}|</nowiki> \geq \delta_j |\mathcal{K}_j(\mathcal{G}^{(j-1)}[V_{i_1}, \ldots, V_{i_j}])|
\end{equation*notation}
we have <nowiki><math> d(\mathcal{G}^{(j)} \vert \mathbf{Q}^{(j-1)}) = d_j \pm \delta_j<\math>
\end{definition}
\begin{definition}[Relative density]
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, <math>j<\math>-edges are regularized versus <math>(j-1)<\math>-edges, for all <math>2\leq j\leq h<\math>.
For <nowiki><math>j \geq 3<\math>, fix some classes <math>V_{i_1}, \ldots, V_{i_j}<\math> of <math>\mathcal{G}^{(1)}<\math> with <math>1 \leq i_1 < \ldots < i_j \leq l<\math>. Suppose <math>r \geq 1<\math> is an integer. Let <math>\mathbf{Q}^{(j-1)} = \{ Q_1^{(j-1)}, \ldots, Q_r^{(j-1)} \}<\math> be a subhypergraph of the induced <math>j<\math>-partite graph <math>\mathcal{G}^{(j-1)}[V_{i_1}, \ldots, V_{i_j}]<\math>. Define the relative density</nowiki>
\begin{definition}[<math>(\delta, \mathbf{d},r)<\math>-regular <math>(l, h)<\math>-complex]
\begin{equation*}
An <math>(l,h)<\math>-complex <math>\mathbf{G}<\math> is a system <math>\{\mathcal{G}^{(j)}\}_{j=1}^h<\math> of <math>l<\math>-partite <math>j<\math> graphs <math>\mathcal{G}^{(j)}<\math> satisfying <math>\mathcal{G}^{(j)} \subset \mathcal{K}_j(\mathcal{G}^{(j-1)})<\math>. Given vectors of positive real numbers <math>\delta = (\delta_2, \ldots, \delta_h)<\math>, <math>\mathbf{d} = (d_2, \ldots, d_h)<\math>, and an integer <math>r \geq 1<\math>, we say <math>(l, h)<\math>-complex is <math>(\delta, \mathbf{d},r)<\math>-regular if
\begin{enumerate}
d(\mathcal{G}^{(j)} \vert \mathbf{Q}^{(j-1)}) = \frac{|\mathcal{G}^{(j)} \cap \cup_{s \in [r]} \mathcal{K}_j(Q_s^{j-1})|}{|\cup_{s \in [r]} \mathcal{K}_j(Q_s^{j-1})|}
\item For each <math>1 \leq i_1 < i_2 \leq l<\math>, <math>\mathcal{G}^{(2)}[V_{i_1},V_{i_2}]<\math> is <math>\delta_2<\math>-regular with density <math>d_2 \pm \delta_2<\math>.
\item For each <math>3 \leq j \leq h<\math>, <math>\mathcal{G}^{(j)}<\math> is (<math>\delta_j, d_j, r<\math>)-regular with respect to <math>\mathcal{G}^{(j-1)}<\math>
\end{enumerateequation*}
\end{definition}
\end{definition}
The following describes the equitable partition that the hypergraph regularity lemma will induce. The <math>(\mu, \delta, \mathbf{d}, r)<\math>-equitable family of partition is a sequence of partitions of 1-edges (vertices), 2-edges (pairs), 3-edges (triples), etc.
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>-edges (<math>\mathcal{G}^{(j-1)}<\math>) have some control over <math>j<\math>-edges (<math>\mathcal{G}^{(j)}<\math>).</nowiki>
\begin{definition}[<math>(\mu, \delta, \mathbf{d}, r)<\math>-equitable partition]
Let <math>\mu > 0<\math> be a real number, <math>r \geq 1<\math> be an integer, and <math>\delta = (\delta_2, \ldots, \delta_{k-1})<\math>, <math>\mathbf{d}=(d_2, \ldots, d_{k-1})<\math> be vectors of positive reals. Let <math>\mathbf{a} = (a_1, \ldots, a_{k-1})<\math> be a vector of positive integers and <math>V<\math> be an <math>n<\math>-element vertex set. We say that a family of partitions <math>\mathcal{P} = \mathcal{P}(k-1, \mathbf{a}) = \{\mathcal{P}^{(1)}\, \ldots, \mathcal{P}^{(k-1)}\}<\math> on <math>V<\math> is <math>(\mu, \delta, \mathbf{d}, r)<\math>-equitable if it satisfies the following
\begin{enumerate}
\begin{definition}[(<nowiki><math>\delta_j, d_j, r<\math>)-regularity]</nowiki>
\item <math>\mathcal{P}^{(1)} = \{V_i \colon i \in [a_1]\}<\math> is equitable vertex partition of <math>V<\math>. That is <math>|V_1| \leq \ldots \leq |V_{a_1}| \leq | V_1| + 1<\math>
\item <math>\mathcal{P}^{(j)}<\math> partitions <math>\mathcal{K}_j(\mathcal{G}^{(1)}) = K_{a_1}^{(j)}(V_1, \ldots, V_{a_1})<\math> so that if <math>P_1^{(j-1)}, \ldots, P_j^{(j-1)} \in \mathcal{P}^{(j-1)}<\math> and
Suppose <nowiki><math>\delta_j, d_j<\math> are positive real numbers and <math>r \geq 1<\math> is an integer. <math>\mathcal{K}_j(\cup_{i=1G}^jP_i{(j-1)}) <\neqmath> is (<math>\emptysetdelta_j, d_j, r<\math>)-regular with respect thento <math>\mathcal{K}_j(\cup_{i=1G}^jP_i{(j-1)})<\math> isif partitionedfor intoany atchoice mostof classes <math>a_jV_{i_1}, \ldots, V_{i_j}<\math> parts,and allany collection of whichsubhypergraphs are<math>\mathbf{Q}^{(j-1)} members= \{ Q_1^{(j-1)}, \ldots, Q_r^{(j-1)} \}<\math> of <math>\mathcal{PG}^{(j-1)}[V_{i_1}, \ldots, V_{i_j}]<\math> satisfying</nowiki>
\item For all but at most <math>\mu n^k<\math> <math>k<\math>-tuples <math>K \in \binom{V}{k}<\math> there is unique <math>(\delta, \mathbf{d},r)<\math>-regular <math>(k, k-1)<\math>-complex <math>\mathbf{P} = \{P^{(j)}\}_{j=1}^{k-1}<\math> such that <math>P^{(j)}<\math> has as members <math>\binom{k}{j}<\math> different partition classes from <math>\mathcal{P}^{(j)}<\math> and <math>K \in \mathcal{K}_k(P^{(k-1)}) \subset \ldots \subset \mathcal{K}_k(P^{(1)})<\math>
\begin{equation*}
\end{enumerate}
\end{definition}
|\cup_{s \in [r]}\mathcal{K}_j(Q_s)^{(j-1)}| \geq \delta_j |\mathcal{K}_j(\mathcal{G}^{(j-1)}[V_{i_1}, \ldots, V_{i_j}])|
\end{equation*}
\begin{definition}
We say that a <math>k<\math>-graph <math>\mathcal{H}^{(k)}<\math> is <math>(\delta_k, r)<\math>-regular with respect to a family of partitions <math>\mathcal{P}<\math> if all but at most <math>\delta_k n^k<\math> <math>k-<\math>edges
we have <nowiki><math> d(\mathcal{G}^{(j)} \vert \mathbf{Q}^{(j-1)}) = d_j \pm \delta_j<\math></nowiki>
<math>K<\math> of <math>\mathcal{H}^{(k)}<\math> have the property that <math>K \in \mathcal{K}_k(\mathcal{G}^{(1)})<\math> and if <math>\mathbf{P} = \{P^{(j)}\}_{j=1}^{k-1}<\math> is unique <math>(k, k-1)<\math>-complex for which <math>K \in \mathcal{K}_k(P^{(k-1)})<\math>, then <math>\mathcal{H}^{(k)}<\math> is <math>(\delta_k, d(\mathcal{H}^{(k)} \vert P^{(k-1)}), r) <\math> regular with respect to <math>\mathcal{P}<\math>.
\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>-edges are regularized versus <math>(j-1)<\math>-edges, for all <math>2\leq j\leq h<\math>.</nowiki>
\begin{theorem}[Hypergraph regularity lemma]
For all positive real <math>\mu<\math>, <math>\delta_k<\math>, functions
\begin{equation*}
\begin{definition}[<nowiki><math>(\delta, \mathbf{d},r)<\math>-regular <math>(l, h)<\math>-complex]</nowiki>
\delta_j \colon (0,1]^{k-j} \to (0,1]
\end{equation*}
An <nowiki><math>(l,h)<\math>-complex <math>\mathbf{G}<\math> is a system <math>\{\mathcal{G}^{(j)}\}_{j=1}^h<\math> of <math>l<\math>-partite <math>j<\math> graphs <math>\mathcal{G}^{(j)}<\math> satisfying <math>\mathcal{G}^{(j)} \subset \mathcal{K}_j(\mathcal{G}^{(j-1)})<\math>. Given vectors of positive real numbers <math>\delta = (\delta_2, \ldots, \delta_h)<\math>, <math>\mathbf{d} = (d_2, \ldots, d_h)<\math>, and an integer <math>r \geq 1<\math>, we say <math>(l, h)<\math>-complex is <math>(\delta, \mathbf{d},r)<\math>-regular if</nowiki>
for <math>j = 2, \ldots, k-1<\math>, and <math>r \colon \mathbb{N} \times (0, 1]^{k-2} \to \mathbb{N}<\math>,
\begin{enumerate}
there exists <math>T_0<\math> and <math>n_0<\math> so that the following holds. For any <math>k<\math>-uniform hypergraph <math>\mathcal{H}^{(k)}<\math> on <math>n \geq n_0<\math> vertices, there exists a family of partitions <math>\mathcal{P} = \mathcal{P}(k-1, \mathbf{a})<\math> and a vector <math>\mathbf{d} = (d_2, \ldots, d_{k-1})<\math> so that, for <math>\mathbf{\delta} = (\delta_2, \ldots, \delta_{k-1})<\math> where <math>\delta_j = \delta_j(d_j, \ldots, d_{k-1})<\math> for all <math>j<\math>, and <math>r = r(a_1, \mathbf{d})<\math>, the following holds
\item For each <nowiki><math>1 \leq i_1 < i_2 \leq l<\math>, <math>\mathcal{G}^{(2)}[V_{i_1},V_{i_2}]<\math> is <math>\delta_2<\math>-regular with density <math>d_2 \pm \delta_2<\math>.</nowiki>
\begin{enumerate}
\item <math>\mathcal{P}<\math> is a <math>(\mu, \mathbf{\delta}, \mathbf{d}, r)<\math>-equitable family of partitions and <math>a_i \leq T_0<\math> for every <math>i = 1, \ldots, k-1<\math>
\item For each <nowiki><math>3 \itemleq j \leq h<\math>, <math>\mathcal{HG}^{(kj)}<\math> is (<math>(\delta_kdelta_j, d_j, r)<\math> )-regular with respect to <math>\mathcal{PG}^{(j-1)}<\math></nowiki>
\end{enumerate}
\end{theoremenumerate}
\end{definition}
\begin{theorem}[Hypergraph counting lemma]
For all integers <math>2 \leq k \leq l<\math> the following holds:
The following describes the equitable partition that the hypergraph regularity lemma will induce. The <nowiki><math>(\mu, \delta, \mathbf{d}, r)<\math>-equitable family of partition is a sequence of partitions of 1-edges (vertices), 2-edges (pairs), 3-edges (triples), etc.</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> and there are integers <math>r<\math> and <math>m_0<\math> so that, with <math>\mathbf{d} = (d_2, \ldots, d_k)<\math>, <math>\delta = (\delta_2, \ldots, \delta_k)<\math>, and <math>m \geq m_0<\math>,
if <math>\mathbf{G} = \{ \mathcal{G}^{(j)}\}_{j=1}^k<\math> is a <math>(\delta, \mathbf{d}, r)<\math>-regular <math>(l,k)<\math> complex with wertex partition <math>\mathcal{G}^{(1)} = V_1 \cup \cdots \cup V_l<\math> and <math>|V_i| = m<\math>, then
\begin{definition}[<nowiki><math>(\mu, \delta, \mathbf{d}, r)<\math>-equitable partition]</nowiki>
\begin{equation*}
|\mathcal{K}_l(\mathcal{G}^{(k)})|</nowiki> = (1 \pm \gamma) \prod_{h = 2}^kd_h^{\binom{l}{h}}\times m^l
Let <nowiki><math>\mu > 0<\math> be a real number, <math>r \geq 1<\math> be an integer, and <math>\delta = (\delta_2, \ldots, \delta_{k-1})<\math>, <math>\mathbf{d}=(d_2, \ldots, d_{k-1})<\math> be vectors of positive reals. Let <math>\mathbf{a} = (a_1, \ldots, a_{k-1})<\math> be a vector of positive integers and <math>V<\math> be an <math>n<\math>-element vertex set. We say that a family of partitions <math>\mathcal{P} = \mathcal{P}(k-1, \mathbf{a}) = \{\mathcal{P}^{(1)}\, \ldots, \mathcal{P}^{(k-1)}\}<\math> on <math>V<\math> is <math>(\mu, \delta, \mathbf{d}, r)<\math>-equitable if it satisfies the following</nowiki>
\end{equation*}
<nowiki> </nowiki>
\begin{enumerate}
\end{theorem}
<nowiki> </nowiki>
\item <nowiki><math>\mathcal{P}^{(1)} = \{V_i \colon i \in [a_1]\}<\math> is equitable vertex partition of <math>V<\math>. That is <math>|V_1| \leq \ldots \leq |V_{a_1}| \leq | V_1| + 1<\math></nowiki>
\section{Applications}
<nowiki> </nowiki>
The main application through which most others follow is the hypergraph removal lemma, which roughly states that given fixed\item <nowiki><math>\mathcal{FP}^{(kj)}<\math> and large partitions <math>\mathcal{HK}_j(\mathcal{G}^{(k1)}<\math>) = <math>k<\math>-uniform hypergraphs, if <math>\mathcalK_{Ha_1}^{(kj)}(V_1, \ldots, V_{a_1})<\math> containsso fewthat copies ofif <math>\mathcal{F}P_1^{(kj-1)}<, \math>ldots, then one can delete few hyperedges in <math>\mathcal{H}P_j^{(kj-1)}< \math>in to eliminate all of the copies of <math>\mathcal{FP}^{(kj-1)}<\math>. To state it more formally,and</nowiki>
<nowiki><math>\mathcal{K}_j(\cup_{i=1}^jP_i{(j-1)}) \neq \emptyset<\math> then <math>\mathcal{K}_j(\cup_{i=1}^jP_i{(j-1)})<\math> is partitioned into at most <math>a_j<\math> parts, all of which are members <math>\mathcal{P}^{(j)}<\math></nowiki>
\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.
\item For all but at most <nowiki><math>\mu n^k<\math> <math>k<\math>-tuples <math>K \in \binom{V}{k}<\math> there is unique <math>(\delta, \mathbf{d},r)<\math>-regular <math>(k, k-1)<\math>-complex <math>\mathbf{P} = \{P^{(j)}\}_{j=1}^{k-1}<\math> such that <math>P^{(j)}<\math> has as members <math>\binom{k}{j}<\math> different partition classes from <math>\mathcal{P}^{(j)}<\math> and <math>K \in \mathcal{K}_k(P^{(k-1)}) \subset \ldots \subset \mathcal{K}_k(P^{(1)})<\math></nowiki>
\end{theorem}
\end{enumerate}
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.
\end{definition}
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. In fact, this approach yields first quantitative bounds for the theorems.
This theorem roughly implies that any dense subset of <math>\ZZ^d<\math> contains any finite pattern of <math>\ZZ^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{definition}
\begin{theorem}[Furstenberg and Katznelson]
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>)
We say that a <nowiki><math>k<\math>-graph <math>\mathcal{H}^{(k)}<\math> is <math>(\delta_k, r)<\math>-regular with respect to a family of partitions <math>\mathcal{P}<\math> if all but at most <math>\delta_k n^k<\math> <math>k-<\math>edges</nowiki>
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>.
<nowiki><math>K<\math> of <math>\mathcal{H}^{(k)}<\math> have the property that <math>K \in \mathcal{K}_k(\mathcal{G}^{(1)})<\math> and if <math>\mathbf{P} = \{P^{(j)}\}_{j=1}^{k-1}<\math> is unique <math>(k, k-1)<\math>-complex for which <math>K \in \mathcal{K}_k(P^{(k-1)})<\math>, then <math>\mathcal{H}^{(k)}<\math> is <math>(\delta_k, d(\mathcal{H}^{(k)} \vert P^{(k-1)}), r) <\math> regular with respect to <math>\mathcal{P}<\math>.</nowiki>
\end{theorem}
Another possible generalization is when it is allowed the dimension to grow.
\end{definition}
\begin{theorem}[Tengan, Tokushige, V.R., and M.S]
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).
\begin{theorem}[Hypergraph regularity lemma]
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. </nowiki>
For all positive real <nowiki><math>\mu<\math>, <math>\delta_k<\math>, functions</nowiki>
\begin{equation*}
\delta_j \colon (0,1]^{k-j} \to (0,1]
\end{equation*}
for <nowiki><math>j = 2, \ldots, k-1<\math>, and <math>r \colon \mathbb{N} \times (0, 1]^{k-2} \to \mathbb{N}<\math>,</nowiki>
there exists <nowiki><math>T_0<\math> and <math>n_0<\math> so that the following holds. For any <math>k<\math>-uniform hypergraph <math>\mathcal{H}^{(k)}<\math> on <math>n \geq n_0<\math> vertices, there exists a family of partitions <math>\mathcal{P} = \mathcal{P}(k-1, \mathbf{a})<\math> and a vector <math>\mathbf{d} = (d_2, \ldots, d_{k-1})<\math> so that, for <math>\mathbf{\delta} = (\delta_2, \ldots, \delta_{k-1})<\math> where <math>\delta_j = \delta_j(d_j, \ldots, d_{k-1})<\math> for all <math>j<\math>, and <math>r = r(a_1, \mathbf{d})<\math>, the following holds</nowiki>
\begin{enumerate}
\item <nowiki><math>\mathcal{P}<\math> is a <math>(\mu, \mathbf{\delta}, \mathbf{d}, r)<\math>-equitable family of partitions and <math>a_i \leq T_0<\math> for every <math>i = 1, \ldots, k-1<\math></nowiki>
\item <nowiki><math>\mathcal{H}^{(k)}<\math> is <math>(\delta_k, r)<\math> regular with respect to <math>\mathcal{P}<\math></nowiki>
\end{enumerate}
\end{theorem}
\begin{theorem}[Hypergraph counting lemma]
For all integers <nowiki><math>2 \leq k \leq l<\math> 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> and there are integers <math>r<\math> and <math>m_0<\math> so that, with <math>\mathbf{d} = (d_2, \ldots, d_k)<\math>, <math>\delta = (\delta_2, \ldots, \delta_k)<\math>, and <math>m \geq m_0<\math>,</nowiki>
if <nowiki><math>\mathbf{G} = \{ \mathcal{G}^{(j)}\}_{j=1}^k<\math> is a <math>(\delta, \mathbf{d}, r)<\math>-regular <math>(l,k)<\math> complex with wertex partition <math>\mathcal{G}^{(1)} = V_1 \cup \cdots \cup V_l<\math> and <math>|V_i| = m<\math>, then</nowiki>
\begin{equation*}
<nowiki> |\mathcal{K}_l(\mathcal{G}^{(k)})| = (1 \pm \gamma) \prod_{h = 2}^kd_h^{\binom{l}{h}}\times m^l</nowiki>
\end{equation*}
\end{theorem}
\section{Applications}
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> 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,</nowiki>
\begin{theorem}[Hypergraph removal lemma]
For all <nowiki><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.</nowiki>
\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> 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.</nowiki>
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. In fact, this approach yields first quantitative bounds for the theorems.
This theorem roughly implies that any dense subset of <nowiki><math>\ZZ^d<\math> contains any finite pattern of <math>\ZZ^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.</nowiki>
\begin{theorem}[Furstenberg and Katznelson]
Let <nowiki><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>)</nowiki>
Moreover, if <nowiki><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>.</nowiki>
\end{theorem}
Another possible generalization is when it is allowed the dimension to grow.
\begin{theorem}[Tengan, Tokushige, V.R., and M.S]
Let <nowiki><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).</nowiki>
In other words, there are some <nowiki><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.</nowiki>
\end{theorem}
| 