Content deleted Content added
→Furstenberg and Katznelson Theorem: move ref out of heading |
mNo edit summary |
||
| (2 intermediate revisions by 2 users not shown) | |||
Line 1:
{{Short description|Mathematical method in extremal graph theory}}
In mathematics, the '''hypergraph regularity method''' is a powerful tool in [[extremal graph theory]] that refers to the combined application of the hypergraph regularity lemma and the associated counting lemma. It is a generalization of the graph regularity method, which refers to the use of [[Szemerédi regularity lemma|Szemerédi's regularity]] and counting lemmas.
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|last1=Rödl|first1=V.|last2=Nagle|first2=B.|last3=Skokan|first3=J.|last4=Schacht|first4=M.|last5=Kohayakawa|first5=Y.|date=2005-06-07|title=The hypergraph regularity method and its applications|journal=Proceedings of the National Academy of Sciences|language=en|volume=102|issue=23|pages=8109–8113|doi=10.1073/pnas.0502771102|issn=0027-8424|pmc=1149431|pmid=15919821 |doi-access=free }}</ref> for alternative versions see [[Terence Tao|Tao]] (2006),<ref>{{Cite journal|last=Tao|first=Terence|authorlink=Terence Tao|date=2006-10-01|title=A variant of the hypergraph removal lemma|journal=[[Journal of Combinatorial Theory]] | series=Series A|language=en|volume=113|issue=7|pages=1257–1280|doi=10.1016/j.jcta.2005.11.006|doi-access=free|issn=0097-3165|arxiv=math/0503572}}</ref> and [[Timothy Gowers|Gowers]] (2007).<ref name=":1">{{Cite journal|last=Gowers|first=William|date=2007-11-01|title=Hypergraph regularity and the multidimensional Szemerédi theorem|journal=Annals of Mathematics|volume=166|issue=3|pages=897–946|doi=10.4007/annals.2007.166.897|issn=0003-486X|doi-access=free|arxiv=0710.3032}}</ref>
== Definitions ==
Line 20 ⟶ 21:
* <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 the main definition that describes the output of hypergraph regularity lemma below.<blockquote>'''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>
| |||