Content deleted Content added
mNo edit summary |
|||
| (24 intermediate revisions by 17 users not shown) | |||
Line 1:
{{Short description|Mathematical method in extremal graph theory}}
Very informally, the hypergraph regularity lemma decomposes any given <math> k </math>-uniform [[hypergraph]] into a random-like object with bounded parts (with an appropriate boundedness and randomness notions) that is usually easier to work with. On the other hand, the hypergraph counting lemma estimates the number of hypergraphs of a given isomorphism class in some collections of the random-like parts. This is an extension of [[Szemerédi regularity lemma|Szemerédi's regularity lemma]] that partitions any given graph into bounded number parts such that edges between the parts behave almost randomly. Similarly, the hypergraph counting lemma is a generalization of [[Szemerédi regularity lemma#Graph counting lemma|the 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 the [[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 [[Vojtěch Rödl|V. Rödl]], B. Nagle, J. Skokan, [[Mathias Schacht|M. Schacht]], and [[Yoshiharu Kohayakawa|Y. Kohayakawa]],<ref>{{Cite journal|
== Definitions ==
In order to state the hypergraph regularity and counting lemmas formally, we need to define several rather technical terms to formalize appropriate notions of [[Pseudorandomness|pseudo-randomness]] (random-likeness) and boundedness, as well as to describe the random-like blocks and partitions.
'''Notation'''
Line 14:
* <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.
The following defines an important notion of relative density, which roughly describes the fraction of <math> j </math>-edges spanned by <math> (j-1) </math>-edges that are in the hypergraph. For example, when <math> j=3 </math>, the quantity <math>d(\mathcal{G}^{(3)} \vert \mathbf{Q}^{(2)})</math> is equal to the fraction of triangles formed by 2-edges in the subhypergraph that are 3-edges. <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>
* 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.
* <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>.</blockquote>Finally, the following defines what it means for a <math> k </math>-uniform hypergraph to be regular with respect to a partition. In particular, this is
== Statements ==
Line 42:
=== [[Hypergraph removal lemma]] ===
<blockquote>For all <math> l \geq k \geq 2 </math> and every <math> \mu > 0 </math>, there exists <math> \zeta > 0 </math> and <math> n_0 > 0 </math> so that the following holds. Suppose <math> \mathcal{F}^{(k)} </math> is a <math> k </math>-uniform hypergraph on <math> l </math> vertices and <math> \mathcal{H}^{(k)} </math> is that on <math> n \geq n_0 </math> vertices. If <math> \mathcal{H}^{(k)} </math> contains at most <math> \zeta n^l </math> copies of <math> \mathcal{F}^{(k)} </math>, then one can delete <math> \mu n^k </math> hyperedges in <math> \mathcal{H}^{(k)} </math> to make it <math> \mathcal{F}^{(k)} </math>-free. </blockquote>One of the original motivations for graph regularity method was to prove
The hypergraph regularity method and hypergraph removal lemma can prove high-dimensional and ring analogues of density version of Szemerédi's theorems, originally proved by Furstenberg and Katznelson.<ref name=":0">{{Cite journal|
This theorem roughly implies that any dense subset of <math> \mathbb{Z}^d </math> contains any finite pattern of <math> \mathbb{Z}^d </math>. The case when <math> d = 1 </math> and the pattern is arithmetic progression of length some length is equivalent to Szemerédi's theorem.<blockquote>
==== Furstenberg and Katznelson Theorem ====
Source:<ref name=":0" /> Let <math> T </math> be a finite subset of <math> \mathbb{R}^d </math> and let <math> \delta > 0 </math> be given. Then there exists a finite subset <math> C \subset \mathbb{R}^d </math> such that
Moreover, if <math> T \subset [-t; t]^d </math> for some <math> t \in \mathbb{N} </math>, then there exists <math> N_0 \in \mathbb{N} </math> such that <math> C = [-N,N]^d </math> has this property for all <math> N \geq N_0 </math>.</blockquote>Another possible generalization that can be proven by the removal lemma is when
==== Tengan, Tokushige, Rödl, and Schacht Theorem ====
Let <math> A </math> be a finite ring. For every <math> \delta > 0 </math>, there exists <math> M_0 </math> such that, for <math> M \geq M_0 </math>, any subset <math> Z \subset A^M </math> with <math> |Z| > \delta |A^M| </math> contains a coset of an isomorphic copy of <math> A </math> (as a left <math> A </math>-module).
Line 57 ⟶ 61:
</blockquote>
== References ==
<!-- Inline citations added to your article will automatically display here. See en.wikipedia.org/wiki/WP:REFB for instructions on how to add citations. -->
{{reflist}}
[[Category:Graph theory]]
| |||