Hypergraph regularity method: Difference between revisions

Revision as of 00:13, 28 November 2021

Revision as of 00:16, 28 November 2021

Line 13:

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.

== StatementsDefinitions ==

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.

Line 37:

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

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

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}

\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{enumerate}

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

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

\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

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

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

\end{enumerate}

\end{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 <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>.

\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

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