Hypergraph regularity method

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.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 11 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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's regularity and counting lemmas.

Very informally, the hypergraph regularity lemma decomposes any given k -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'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 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 V. Rödl, B. Nagle, J. Skokan, M. Schacht, and Y.…

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's regularity and counting lemmas.

Very informally, the hypergraph regularity lemma decomposes any given k -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'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 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 V. Rödl, B. Nagle, J. Skokan, M. Schacht, and Y. Kohayakawa, for alternative versions see Tao (2006), and Gowers (2007). \mathcal{G}^{(j)} is an l -partite j -graph on vertex partition \mathcal{G}^{(1)} = V_1 \sqcup \ldots \sqcup V_l . \mathcal{K}_j(\mathcal{G}^{(i)}) is the family of all j -element vertex sets that span the clique K_j^{(i)} in \mathcal{G}^{(i)} .

In particular, \mathcal{K}_j(\mathcal{G}^{(1)}) = K_l^{(j)}(V_1, \ldots, V_l) is a complete l -partite j -graph. The following defines an important notion of relative density, which roughly describes the fraction of j -edges spanned by (j-1) -edges that are in the hypergraph.

For example, when j=3 , the quantity d(\mathcal{G}^{(3)} \vert \mathbf{Q}^{(2)}) is equal to the fraction of triangles formed by 2-edges in the subhypergraph that are 3-edges. Definition [Relative density]. For j \geq 3 , fix some classes V_{i_1}, \ldots, V_{i_j} of \mathcal{G}^{(1)} with 1 \leq i_1 .

Suppose r \geq 1 is an integer. Let \mathbf{Q}^{(j-1)} = \{ Q_1^{(j-1)}, \ldots, Q_r^{(j-1)} \} be a subhypergraph of the induced j -partite graph \mathcal{G}^{(j-1)}[V_{i_1}, \ldots, V_{i_j}] .

Define the relative density d\left(\mathcal{G}^{(j)} \vert \mathbf{Q}^{(j-1)}\right) = \frac{\left|\mathcal{G}^{(j)} \cap \cup_{s \in [r]} \mathcal{K}_j(Q_s^{j-1})\right|}{\left|\cup_{s \in [r]} \mathcal{K}_j(Q_s^{j-1})\right|} . What follows is the appropriate notion of pseudorandomness that the regularity method will use.

Informally, by this concept of regularity, (j-1) -edges ( \mathcal{G}^{(j-1)} ) have some control over j -edges ( \mathcal{G}^{(j)} ). More precisely, this defines a setting where density of j edges in large subhypergraphs is roughly the same as one would expect based on the relative density alone. Formally, Definition [( \delta_j, d_j, r )-regularity].

Suppose \delta_j, d_j are positive real numbers and r \geq 1 is an integer. \mathcal{G}^{(j)} is ( \delta_j, d_j, r )-regular with respect to \mathcal{G}^{(j-1)} if for any choice of classes V_{i_1}, \ldots, V_{i_j} and any collection of subhypergraphs \mathbf{Q}^{(j-1)} = \{ Q_1^{(j-1)}, \ldots, Q_r^{(j-1)} \} of \mathcal{G}^{(j-1)}[V_{i_1}, \ldots, V_{i_j}] satisfying \left|\cup_{s \in [r]}\mathcal{K}_j(Q_s)^{(j-1)}\right| \geq \delta_j \left|\mathcal{K}_j(\mathcal{G}^{(j-1)}[V_{i_1}, \ldots, V_{i_j}])\right| we have d(\mathcal{G}^{(j)} \vert \mathbf{Q}^{(j-1)}) = d_j \pm \delta_j . Roughly speaking, the following describes the pseudorandom blocks into which the hypergraph regularity lemma decomposes any large enough hypergraph. In Szemerédi regularity, 2-edges are regularized versus 1-edges (vertices).

In this generalized notion, j -edges are regularized versus (j-1) -edges for all 2\leq j\leq h . More precisely, this defines a notion of regular hypergraph called (l, h) -complex, in which existence of j -edge implies existence of all underlying (j-1) -edges, as well as their relative regularity. For example, if \{x,y,z\} is a 3-edge then \{x,y\} , \{x,z\} , and \{y,z\} are 2-edges in the complex.

Moreover, the density of 3-edges over all possible triangles made by 2-edges is roughly the same in every collection of subhypergraphs. Definition [ (\delta, \mathbf{d},r) -regular (l, h) -complex]. An (l,h) -complex \mathbf{G} is a system \{\mathcal{G}^{(j)}\}_{j=1}^h of l -partite j graphs \mathcal{G}^{(j)} satisfying \mathcal{G}^{(j)} \subset \mathcal{K}_j(\mathcal{G}^{(j-1)}) .

Given vectors of positive real numbers \delta = (\delta_2, \ldots, \delta_h) , \mathbf{d} = (d_2, \ldots, d_h) , and an integer r \geq 1 , we say (l, h) -complex is (\delta, \mathbf{d},r) -regular if For each 1 \leq i_1 , \mathcal{G}^{(2)}[V_{i_1},V_{i_2}] is \delta_2 -regular with density d_2 \pm \delta_2 . For each 3 \leq j \leq h , \mathcal{G}^{(j)} is ( \delta_j, d_j, r )-regular with respect to \mathcal{G}^{(j-1)} .

The following describes the equitable partition that the hypergraph regularity lemma will induce. A (\mu, \delta, \mathbf{d}, r) -equitable family of partition is a sequence of partitions of 1-edges (vertices), 2-edges (pairs), 3-edges (triples), etc. This is an important distinction from the partition obtained by Szemerédi's regularity lemma, where only vertices are being partitioned.

In fact, Gowers demonstrated that solely vertex partition can not give a sufficiently strong notion of regularity to imply Hypergraph counting lemma. Definition [ (\mu, \delta, \mathbf{d}, r) -equitable partition]. Let \mu > 0 be a real number, r \geq 1 be an integer, and \delta = (\delta_2, \ldots, \delta_{k-1}) , \mathbf{d}=(d_2, \ldots, d_{k-1}) be vectors of positive reals.

Let \mathbf{a} = (a_1, \ldots, a_{k-1}) be a vector of positive integers and V be an n -element vertex set. We say that a family of partitions \mathcal{P} = \mathcal{P}(k-1, \mathbf{a}) = \{\mathcal{P}^{(1)}\, \ldots, \mathcal{P}^{(k-1)}\} on V is (\mu, \delta, \mathbf{d}, r) -equitable if it satisfies the following: \mathcal{P}^{(1)} = \{V_i \colon i \in [a_1]\} is equitable vertex partition of V . That is |V_1| \leq \ldots \leq |V_{a_1}| \leq | V_1| + 1 . \mathcal{P}^{(j)} partitions \mathcal{K}_j(\mathcal{G}^{(1)}) = K_{a_1}^{(j)}(V_1, \ldots, V_{a_1}) so that if P_1^{(j-1)}, \ldots, P_j^{(j-1)} \in \mathcal{P}^{(j-1)} and \mathcal{K}_j(\cup_{i=1}^jP_i^{(j-1)}) \neq \emptyset then \mathcal{K}_j(\cup_{i=1}^jP_i^{(j-1)}) is partitioned into at most a_j parts, all of which are members \mathcal{P}^{(j)} .

For all but at most \mu n^k k -tuples K \in \binom{V}{k} there is unique (\delta, \mathbf{d},r) -regular (k, k-1) -complex \mathbf{P} = \{P^{(j)}\}_{j=1}^{k-1} such that P^{(j)} has as members \binom{k}{j} different partition classes from \mathcal{P}^{(j)} and K \in \mathcal{K}_k(P^{(k-1)}) \subset \ldots \subset \mathcal{K}_k(P^{(1)}) . Finally, the following defines what it means for a k -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. Definition [Regularity with respect to a partition].

We say that a k -graph \mathcal{H}^{(k)} is (\delta_k, r) -regular with respect to a family of partitions \mathcal{P} if all but at most \delta_k n^k k- edges K of \mathcal{H}^{(k)} have the property that K \in \mathcal{K}_k(\mathcal{G}^{(1)}) and if \mathbf{P} = \{P^{(j)}\}_{j=1}^{k-1} is unique (k, k-1) -complex for which K \in \mathcal{K}_k(P^{(k-1)}) , then \mathcal{H}^{(k)} is (\delta_k, d(\mathcal{H}^{(k)} \vert P^{(k-1)}), r) regular with respect to \mathcal{P} . For all positive real \mu , \delta_k , and functions r \, \colon \mathbb{N} \times (0, 1]^{k-2} \to \mathbb{N} , \delta_j \, \colon (0,1]^{k-j} \to (0,1] for j = 2, \ldots, k-1 there exists T_0 and n_0 so that the following holds.

For any k -uniform hypergraph \mathcal{H}^{(k)} on n \geq n_0 vertices, there exists a family of partitions \mathcal{P} = \mathcal{P}(k-1, \mathbf{a}) and a vector \mathbf{d} = (d_2, \ldots, d_{k-1}) so that, for r = r(a_1, \mathbf{d}) and \mathbf{\delta} = (\delta_2, \ldots, \delta_{k-1}) where \delta_j = \delta_j(d_j, \ldots, d_{k-1}) for all j , the following holds. \mathcal{P} is a (\mu, \mathbf{\delta}, \mathbf{d}, r) -equitable family of partitions and a_i \leq T_0 for every i = 1, \ldots, k-1 . \mathcal{H}^{(k)} is (\delta_k, r) regular with respect to \mathcal{P} . For all integers 2 \leq k \leq l the following holds: \forall \gamma > 0 \; \; \forall d_k > 0 \; \; \exists \delta_k > 0 \;\; \forall d_{k-1} > 0 \; \; \exists \delta_{k-1} > 0 \; \cdots \; \forall d_2 > 0 \; \; \exists \delta_2>0 and there are integers r and m_0 so that, with \mathbf{d} = (d_2, \ldots, d_k) , \delta = (\delta_2, \ldots, \delta_k) , and m \geq m_0 , if \mathbf{G} = \{ \mathcal{G}^{(j)}\}_{j=1}^k is a (\delta, \mathbf{d}, r) -regular (l,k) complex with vertex partition \mathcal{G}^{(1)} = V_1 \cup \cdots \cup V_l and |V_i| = m , then \left|\mathcal{K}_l(\mathcal{G}^{(k)})\right| = (1 \pm \gamma) \prod_{h = 2}^kd_h^{\binom{l}{h}}\times m^l . This theorem roughly implies that any dense subset of \mathbb{Z}^d contains any finite pattern of \mathbb{Z}^d . The case when d = 1 and the pattern is arithmetic progression of length some length is equivalent to Szemerédi's theorem.

Moreover, if T \subset [-t; t]^d for some t \in \mathbb{N} , then there exists N_0 \in \mathbb{N} such that C = [-N,N]^d has this property for all N \geq N_0 . Another possible generalization that can be proven by the removal lemma is when the dimension is allowed to grow.

In other words, there are some \mathbf{r}, \mathbf{u} \in A^M such that r + \varphi(A) \subset Z , where \varphi \colon A \to A^M , \varphi(a)=a \mathbf{u} is an injection.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1247154057 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001247154057 · captured 1727050147.0 · version history

Cite this page as: encyclopegia.org, “Hypergraph regularity method”, snapshot enwiki-001247154057. https://encyclopegia.org/a/hypergraph-regularity-method

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.