Content deleted Content added
No edit summary |
No edit summary |
||
Line 1:
{{AfC submission|t||ts=20211127234938|u=Lepsvera|ns=118|demo=}}
====== <!-- Important, do not remove this line before article has been created. --> ====== == Introduction ==
Line 6 ⟶ 8:
Very informally, hypergraph regularity lemma decomposes any given <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. 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.
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. The following formulations are due to [insert names], for alternative versions see [insert names]. ▼
▲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.
== Definitions ==
'''Notation'''
* <math> K_j^{(k)} </math> denotes a <math> k </math>-uniform clique on <math> j </math> vertices▼
* <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>
* <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>
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
<math>d\left(\mathcal{G}^{(j)} \vert \mathbf{Q}^{(j-1)}\right) = \frac{\left|\mathcal{G}^{(j)} \cap \cup_{s \in [r]} \mathcal{K}_j(Q_s^{j-1})\right|}{\left|\cup_{s \in [r]} \mathcal{K}_j(Q_s^{j-1})\right|}</math></blockquote>The following is the appropriate notion of pseudorandomness that the regularity method will use. Informally, by this concept of regularity, <math> j-1 </math>-edges (<math> \mathcal{G}^{(j-1)} </math>) have some control over <math> j </math>-edges (<math> \mathcal{G}^{(j)} </math>).<blockquote>'''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
<math>\left|\cup_{s \in [r]}\mathcal{K}_j(Q_s)^{(j-1)}\right| \geq \delta_j \left|\mathcal{K}_j(\mathcal{G}^{(j-1)}[V_{i_1}, \ldots, V_{i_j}])\right|</math>
we have <math> d(\mathcal{G}^{(j)} \vert \mathbf{Q}^{(j-1)}) = d_j \pm \delta_j </math></blockquote>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>.<blockquote>'''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
* 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>.
* 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>
</blockquote>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. <blockquote>'''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
Line 43 ⟶ 45:
* 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>
▲==== Regularity with respect to a partition ====
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>.</blockquote>
| |||