Content deleted Content added
No edit summary |
|||
Line 7:
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
== Definitions ==
Line 71 ⟶ 70:
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).
In other words, there are some <math> \mathbf{r}, \mathbf{u} \in A^M </math> such that <math> r + \varphi(A) \subset Z </math>, where <math> \varphi \colon A \to A^M </math>, <math> \varphi(a)=a \mathbf{u} </math> is an injection.</blockquote>
| |||