Content deleted Content added
Line 4:
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 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, hypergraph counting lemma is a generalization of [[Szemerédi regularity lemma#Graph counting lemma|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 [[Vojtěch Rödl|V. Rödl]], B. Nagle, J. Skokan, [[Mathias Schacht|M. Schacht]], and [[Yoshiharu Kohayakawa|Y. Kohayakawa]]<ref>{{Cite journal|last=Rödl|first=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|url=https://www.pnas.org/content/102/23/8109|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=PMC1149431|pmid=15919821}}</ref>, for alternative versions see [[Terence Tao|Tao]] (2006)<ref>{{Cite journal|last=Tao|first=Terence|date=2006-10-01|title=A variant of the hypergraph removal lemma|url=https://www.sciencedirect.com/science/article/pii/S0097316505002177|journal=Journal of Combinatorial Theory, Series A|language=en|volume=113|issue=7|pages=1257–1280|doi=10.1016/j.jcta.2005.11.006|issn=0097-3165}}</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|url=http://doi.org/10.4007/annals.2007.166.897|journal=Annals of Mathematics|volume=166|issue=3|pages=897–946|doi=10.4007/annals.2007.166.897|issn=0003-486X}}</ref>.
== Definitions ==
Line 19:
* 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. This is important distinction from the partition obtained by Szemerédi's regularity lemma, where only vertices are being partitioned. In fact, Gowers<ref name=":1" /> demonstrated that solely vertex partition can not give sufficiently strong notion of regularity to imply Hypergraph counting lemma. <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> .
| |||