Hypergraph regularity method: Difference between revisions

Revision as of 00:16, 28 November 2021

Revision as of 00:21, 28 November 2021

Line 44:

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

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.

Line 51 ⟶ 50:

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

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

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

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

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

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

== Statements ==

\begin{theorem}[=== Hypergraph regularity lemma] ===

For all positive real <math> \mu </math>, <math> \delta_k </math>, functions <math>\delta_j \colon (0,1]^{k-j} \to (0,1]</math>for <math> j = 2, \ldots, k-1 </math>, and <math> r \colon \mathbb{N} \times (0, 1]^{k-2} \to \mathbb{N} </math>,

\begin{theorem}[Hypergraph regularity lemma]

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

\begin{equation*}

\delta_j \colon (0,1]^{k-j} \to (0,1]

\end{equation*}

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

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

\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* <math> \mathcal{H}^{(k)P} </math> is a <math> (\delta_kmu, \mathbf{\delta}, \mathbf{d}, r) </math>-equitable regularfamily withof respectpartitions toand <math> a_i \mathcal{P}leq T_0 </math> for every <math> i = 1, \ldots, k-1 </math>

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

\end{enumerate}

\end{theorem}

\begin{theorem}[=== Hypergraph counting lemma] ===

\begin{theorem}[Hypergraph counting lemma]

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

<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{equation*}

<math>\left|\mathcal{K}_l(\mathcal{G}^{(k)})\right| = (1 \pm \gamma) \prod_{h = 2}^kd_h^{\binom{l}{h}}\times m^l</math>

\end{equation*}

\end{theorem}

== 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,