Content deleted Content added
No edit summary |
|||
Line 11:
'''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> is a complete <math> l </math>-partite <math> j </math>-graph.
<blockquote>'''Definition [Relative density].''' 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>In what follows 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>). Formally,<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:
* <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>.
* 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>.
'''Definition [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>
Line 30:
=== Hypergraph regularity lemma ===
For all positive real <math> \mu </math>, <math> \delta_k </math>, and functions <math> r \, \colon \mathbb{N} \times (0, 1]^{k-2} \to \mathbb{N} </math>, <math>\delta_j \, \colon (0,1]^{k-j} \to (0,1]</math> for <math> j = 2, \ldots, k-1 </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> r = r(a_1, \mathbf{d}) </math> and <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>, the following holds.
* <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>.
* <math> \mathcal{H}^{(k)} </math> is <math> (\delta_k, r) </math> regular with respect to <math> \mathcal{P} </math>.
=== Hypergraph counting lemma ===
Line 39:
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 vertex partition <math> \mathcal{G}^{(1)} = V_1 \cup \cdots \cup V_l </math> and <math> |V_i| = m </math>, then
<math>\left|\mathcal{K}_l(\mathcal{G}^{(k)})\right| = (1 \pm \gamma) \prod_{h = 2}^kd_h^{\binom{l}{h}}\times m^l</math>.
== 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,
| |||