Content deleted Content added
Citation bot (talk | contribs) Alter: pmc. Add: doi, arxiv, s2cid, doi-access, authors 1-1. Removed proxy/dead URL that duplicated identifier. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | #UCB_toolbar |
No edit summary |
||
Line 8:
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|
====== <!-- Important, do not remove this line before article has been created. --> ======
Line 47:
<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,<blockquote>
=== [[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. </blockquote>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|
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>
| |||