Content deleted Content added
m Fix PMC warnings |
Removed intro section |
||
Line 3:
{{AfC topic|stem}}
{{AfC submission|||ts=20211128020319|u=Lepsvera|ns=118}}
Hypergraph regularity method is a powerful tool that refers to the combined application of hypergraph regularity lemma and associated counting lemma. It is a generalization of graph regularity method, which refers to the use of [[Szemerédi regularity lemma|Szemerédi's regularity]] and counting lemmas.
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's regularity lemma that decomposes any given graph into pseudorandom blocks, namely <math> \varepsilon </math>-regular pairs, and 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=
====== <!-- Important, do not remove this line before article has been created. --> ======
Line 47 ⟶ 46:
<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,
=== [[Hypergraph removal lemma]] ===
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 </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.
One of the original motivations for graph regularity method was to prove a [[Szemerédi's theorem]], which states that every dense subset of <math> \mathbb{Z} </math> contains an arithmetic progression of arbitrary length. In fact, by a relatively simple application of [[triangle removal lemma]], one can prove that every dense subset of <math> \mathbb{Z} </math> contains an arithmetic progression of length 3. 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|last=Furstenberg|first=Hillel|last2=Katznelson|first2=Yitzhak|date=1978|title=An ergodic Szemeredi theorem for commuting transformations|journal=J. Analyse Math.|volume=34|pages=275–291}}</ref>. In fact, this approach yields first quantitative bounds for the theorems.
| |||