Hypergraph regularity method: Difference between revisions

Revision as of 21:55, 9 December 2021

Revision as of 21:56, 9 December 2021

Line 15:

* <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>. ThisMore precisely, this defines a notion of regular hypergraph called '''<math> (l, h) </math>'''-complex, in which existence of <math> j </math>-edge implies existence of all underlying <math> (j-1) </math>-edges, as well as their relative regularity. For example, if <math> \{x,y,z\} </math> is a 3-edge then <math> \{x,y\} </math>,<math> \{x,z\} </math>, and <math> \{y,z\} </math> are 2-edges in the complex. Moreover, the density of 3-edges over all possible triangles made by 2-edges is roughly the same in every collection of subhypergraphs.<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>.