Английская Википедия:Hall-type theorems for hypergraphs

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Шаблон:Short description

In the mathematical field of graph theory, Hall-type theorems for hypergraphs are several generalizations of Hall's marriage theorem from graphs to hypergraphs. Such theorems were proved by Ofra Kessler,[1][2] Ron Aharoni,[3][4] Penny Haxell,[5][6] Roy Meshulam,[7] and others.

Preliminaries

Hall's marriage theorem provides a condition guaranteeing that a bipartite graph Шаблон:Math admits a perfect matching, or - more generally - a matching that saturates all vertices of Шаблон:Mvar. The condition involves the number of neighbors of subsets of Шаблон:Mvar. Generalizing Hall's theorem to hypergraphs requires a generalization of the concepts of bipartiteness, perfect matching, and neighbors.

1. Bipartiteness: The notion of a bipartiteness can be extended to hypergraphs in many ways (see bipartite hypergraph). Here we define a hypergraph as bipartite if it is exactly 2-colorable, i.e., its vertices can be 2-colored such that each hyperedge contains exactly one yellow vertex. In other words, Шаблон:Mvar can be partitioned into two sets Шаблон:Mvar and Шаблон:Mvar, such that each hyperedge contains exactly one vertex of Шаблон:Mvar.[1] A bipartite graph is a special case in which each edge contains exactly one vertex of Шаблон:Mvar and also exactly one vertex of Шаблон:Mvar; in a bipartite hypergraph, each hyperedge contains exactly one vertex of Шаблон:Mvar but may contain zero or more vertices of Шаблон:Mvar. For example, the hypergraph Шаблон:Math with Шаблон:Math and Шаблон:Math is bipartite with Шаблон:Math and Шаблон:Math

2. Perfect matching: A matching in a hypergraph Шаблон:Math is a subset Шаблон:Mvar of Шаблон:Mvar, such that every two hyperedges of Шаблон:Mvar are disjoint. If Шаблон:Mvar is bipartite with parts Шаблон:Mvar and Шаблон:Mvar, then the size of each matching is obviously at most Шаблон:Math. A matching is called Шаблон:Mvar-perfect (or Шаблон:Mvar-saturating) if its size is exactly Шаблон:Math. In other words: every vertex of Шаблон:Mvar appears in exactly one hyperedge of Шаблон:Mvar. This definition reduces to the standard definition of a Шаблон:Mvar-perfect matching in a bipartite graph.

3. Neighbors: Given a bipartite hypergraph Шаблон:Math and a subset Шаблон:Math of Шаблон:Mvar, the neighbors of Шаблон:Math are the subsets of Шаблон:Mvar that share hyperedges with vertices of Шаблон:Math. Formally:

<math>N_H(Y_0) := \{X_0\subseteq X ~~|~~ \exists y_0\in Y_0: ~\{y_0\}\cup X_0 \in E \}.</math>

For example, in the hypergraph from point 1, we have: Шаблон:Math and Шаблон:Math and Шаблон:Math Note that, in a bipartite graph, each neighbor is a singleton - the neighbors are just the vertices of Шаблон:Mvar that are adjacent to one or more vertices of Шаблон:Math. In a bipartite hypergraph, each neighbor is a set - the neighbors are the subsets of Шаблон:Mvar that are "adjacent" to one or more vertices of Шаблон:Math.

Since Шаблон:Math contains only subsets of Шаблон:Mvar, one can define a hypergraph in which the vertex set is Шаблон:Mvar and the edge set is Шаблон:Math. We call it the neighborhood-hypergraph of Шаблон:Math and denote it:

<math>H_H(Y_0) := (X, N_H(Y_0)).</math>

Note that, if Шаблон:Mvar is a simple bipartite graph, the neighborhood-hypergraph of every Шаблон:Math contains just the neighbors of Шаблон:Math in Шаблон:Mvar, each of which with a self-loop.

Insufficiency of Hall's condition

Hall's condition requires that, for each subset Шаблон:Math of Шаблон:Mvar, the set of neighbors of Шаблон:Math is sufficiently large. With hypergraphs this condition is insufficient. For example, consider the tripartite hypergraph with edges:

{ {1, a, A}, {2, a, B} }

Let Шаблон:Math Every vertex in Шаблон:Mvar has a neighbor, and Шаблон:Mvar itself has two neighbors: Шаблон:Math But there is no Шаблон:Mvar-perfect matching since both edges overlap. One could try to fix it by requiring that Шаблон:Math contain at least Шаблон:Math disjoint edges, rather than just Шаблон:Math edges. In other words: Шаблон:Math should contain a matching of size at least Шаблон:Math. The largest size of a matching in a hypergraph Шаблон:Mvar is called its matching number and denoted by Шаблон:Math (thus Шаблон:Mvar admits a Шаблон:Mvar-perfect matching if and only if Шаблон:Math). However, this fix is insufficient, as shown by the following tripartite hypergraph:

{ {1, a, A}, {1, b, B}, {2, a, B}, {2, b, A} }

Let Шаблон:Math Again every vertex in Шаблон:Mvar has a neighbor, and Шаблон:Mvar itself has four neighbors: Шаблон:Math Moreover, Шаблон:Math since Шаблон:Math admits a matching of size 2, e.g. Шаблон:Math However, H does not admit a Шаблон:Mvar-perfect matching, since every hyperedge that contains 1 overlaps every hyperedge that contains 2.

Thus, to guarantee a perfect matching, a stronger condition is needed. Various such conditions have been suggested.

Aharoni's conditions: largest matching

Let Шаблон:Math be a bipartite hypergraph (as defined in 1. above), in which the size of every hyperedge is exactly Шаблон:Mvar, for some integer Шаблон:Math. Suppose that, for every subset Шаблон:Math of Шаблон:Mvar, the following inequality holds:

<math>\nu(N_H(Y_0)) \geq (r-1)\cdot (|Y_0| - 1) + 1</math>

In words: the neighborhood-hypergraph of Шаблон:Math admits a matching larger than Шаблон:Math. Then Шаблон:Mvar admits a Шаблон:Mvar-perfect matching (as defined in 2. above).

This was first conjectured by Aharoni.[3] It was proved with Ofra Kessler for bipartite hypergraphs in which Шаблон:Math[1] and for Шаблон:Math.[2] It was later proved for all Шаблон:Mvar-uniform hypergraphs.[6]Шаблон:Rp

In simple graphs

For a bipartite simple graph Шаблон:Math, and Aharoni's condition becomes:

<math>\nu(H_H(Y_0)) \geq |Y_0|.</math>

Moreover, the neighborhood-hypergraph (as defined in 3. above) contains just singletons - a singleton for every neighbor of Шаблон:Math. Since singletons do not intersect, the entire set of singletons is a matching. Hence, Шаблон:Math the number of neighbors of Шаблон:Math. Thus, Aharoni's condition becomes, for every subset Шаблон:Math of Шаблон:Mvar:

<math>|N_H(Y_0)| \geq |Y_0|.</math>

This is exactly Hall's marriage condition.

Tightness

The following example shows that the factor Шаблон:Math cannot be improved. Choose some integer Шаблон:Math. Let Шаблон:Math be the following Шаблон:Mvar-uniform bipartite hypergraph:

Note that edge Шаблон:Mvar in Шаблон:Mvar meets all edges in Шаблон:Mvar.

This Шаблон:Mvar does not admit a Шаблон:Mvar-perfect matching, since every hyperedge that contains Шаблон:Mvar intersects all hyperedges in Шаблон:Mvar for some Шаблон:Math.

However, every subset Шаблон:Math of Шаблон:Mvar satisfies the following inequality

<math>\nu(H_H(Y_0)) \geq (r-1)\cdot (|Y_0| - 1)</math>

since Шаблон:Math contains at least Шаблон:Math hyperedges, and they are all disjoint.

Fractional matchings

The largest size of a fractional matching in Шаблон:Mvar is denoted by Шаблон:Math. Clearly Шаблон:Math. Suppose that, for every subset Шаблон:Math of Шаблон:Mvar, the following weaker inequality holds:

<math>\nu^*(H_H(Y_0)) \geq (r-1)\cdot (|Y_0| - 1) +1</math>

It was conjectured that in this case, too, Шаблон:Mvar admits a Шаблон:Mvar-perfect matching. This stronger conjecture was proved for bipartite hypergraphs in which Шаблон:Math.[4]

Later it was proved[4] that, if the above condition holds, then Шаблон:Mvar admits a Шаблон:Mvar-perfect fractional matching, i.e., Шаблон:Math. This is weaker than having a Шаблон:Mvar-perfect matching, which is equivalent to Шаблон:Math.

Haxell's condition: smallest transversal

A transversal (also called vertex-cover or hitting-set) in a hypergraph Шаблон:Math is a subset Шаблон:Mvar of Шаблон:Mvar such that every hyperedge in Шаблон:Mvar contains at least one vertex of Шаблон:Mvar. The smallest size of a transversal in Шаблон:Mvar is denoted by Шаблон:Math.

Let Шаблон:Math be a bipartite hypergraph in which the size of every hyperedge is at most Шаблон:Mvar, for some integer Шаблон:Math. Suppose that, for every subset Шаблон:Math of Шаблон:Mvar, the following inequality holds:

<math>\tau(H_H(Y_0)) \geq (2r-3)\cdot (|Y_0| - 1) + 1</math>

In words: the neighborhood-hypergraph of Шаблон:Math has no transversal of size Шаблон:Math or less.

Then, Шаблон:Mvar admits a Шаблон:Mvar-perfect matching (as defined in 2. above).[5]Шаблон:Rp

In simple graphs

For a bipartite simple graph Шаблон:Math so Шаблон:Math, and Haxell's condition becomes:

<math>\tau(H_H(Y_0)) \geq |Y_0|.</math>

Moreover, the neighborhood-hypergraph (as defined in 3. above) contains just singletons - a singleton for every neighbor of Шаблон:Math. In a hypergraph of singletons, a transversal must contain all vertices. Hence, Шаблон:Math the number of neighbors of Шаблон:Math. Thus, Haxell's condition becomes, for every subset Шаблон:Math of Шаблон:Mvar:

<math>|N_H(Y_0)| \geq |Y_0|.</math>

This is exactly Hall's marriage condition. Thus, Haxell's theorem implies Hall's marriage theorem for bipartite simple graphs.

Tightness

The following example shows that the factor Шаблон:Math cannot be improved. Let Шаблон:Math be an Шаблон:Mvar-uniform bipartite hypergraph with:

  • <math>Y = \{ 0,1 \} </math>
  • <math>X = \{ x_{ij} : 1 \leq i,j \leq r-1 \}</math> [so Шаблон:Math].
  • <math>E = E_0 \cup E_1,</math> where:

This Шаблон:Mvar does not admit a Шаблон:Mvar-perfect matching, since every hyperedge that contains 0 intersects every hyperedge that contains 1.

However, every subset Шаблон:Math of Шаблон:Mvar satisfies the following inequality:

<math>\tau(H_H(Y_0)) \geq (2r-3)\cdot (|Y_0| - 1)</math>

It is only slightly weaker (by 1) than required by Haxell's theorem. To verify this, it is sufficient to check the subset Шаблон:Math, since it is the only subset for which the right-hand side is larger than 0. The neighborhood-hypergraph of Шаблон:Mvar is Шаблон:Math where:

<math>E_{00} = \{ \{ x_{i1}, \ldots, x_{i(r-1)} \} | 1 \leq i \leq r-1 \}</math>
<math>E_{11} = \{ \{ x_{1j[1]}, \ldots, x_{(r-1) j[r-1]} \} | 1 \leq j[k] \leq r-1</math>
for <math>1 \leq k \leq r-1 \}</math>

One can visualize the vertices of Шаблон:Mvar as arranged on an Шаблон:Math grid. The hyperedges of Шаблон:Math are the Шаблон:Math rows. The hyperedges of Шаблон:Math are the Шаблон:Math selections of a single element in each row and each column. To cover the hyperedges of Шаблон:Math we need Шаблон:Math vertices - one vertex in each row. Since all columns are symmetric in the construction, we can assume that we take all the vertices in column 1 (i.e., Шаблон:Math for each Шаблон:Mvar in Шаблон:Math. Now, since Шаблон:Math contains all columns, we need at least Шаблон:Math additional vertices - one vertex for each column Шаблон:Math All in all, each transversal requires at least Шаблон:Math vertices.

Algorithms

Haxell's proof is not constructive. However, Chidambaram Annamalai proved that a perfect matching can be found efficiently under a slightly stronger condition.[8]

For every fixed choice of Шаблон:Math and Шаблон:Math, there exists an algorithm that finds a Шаблон:Mvar-perfect matching in every Шаблон:Mvar-uniform bipartite hypergraph satisfying, for every subset Шаблон:Math of Шаблон:Mvar:

<math>\tau(H_H(Y_0)) \geq (2r-3 +\epsilon)\cdot (|Y_0| - 1) + 1</math>

In fact, in any Шаблон:Mvar-uniform hypergraph, the algorithm finds either a Шаблон:Mvar-perfect matching, or a subset Шаблон:Math violating the above inequality.

The algorithm runs in time polynomial in the size of Шаблон:Mvar, but exponential in Шаблон:Mvar and Шаблон:Math.

It is an open question whether there exists an algorithm with run-time polynomial in either Шаблон:Mvar or Шаблон:Math (or both).

Similar algorithms have been applied for solving problems of fair item allocation, in particular the santa-claus problem.[9][10][11]

Aharoni–Haxell conditions: smallest pinning sets

We say that a set Шаблон:Mvar of edges pins another set Шаблон:Mvar of edges if every edge in Шаблон:Mvar intersects some edge in Шаблон:Mvar.[6] The width of a hypergraph Шаблон:Math, denoted Шаблон:Math, is the smallest size of a subset of Шаблон:Mvar that pins Шаблон:Mvar.[7] The matching width of a hypergraph Шаблон:Mvar, denoted Шаблон:Math, is the maximum, over all matchings Шаблон:Mvar in Шаблон:Mvar, of the minimum size of a subset of Шаблон:Mvar that pins Шаблон:Mvar.[12] Since Шаблон:Mvar contains all matchings in Шаблон:Mvar, the width of H is obviously at least as large as the matching-width of Шаблон:Mvar.

Aharoni and Haxell proved the following condition:

Let Шаблон:Math be a bipartite hypergraph. Suppose that, for every subset Шаблон:Math of Шаблон:Mvar, the following inequality holds:

<math>mw(N_H(Y_0)) \geq |Y_0|</math>

[in other words: Шаблон:Math contains a matching Шаблон:Math such that at least Шаблон:Math disjoint edges from Шаблон:Math are required for pinning Шаблон:Math]. Then, Шаблон:Mvar admits a Шаблон:Mvar-perfect matching.[6]Шаблон:Rp

They later extended this condition in several ways, which were later extended by Meshulam as follows:

Let Шаблон:Math be a bipartite hypergraph. Suppose that, for every subset Шаблон:Math of Шаблон:Mvar, at least one of the following conditions hold:

<math>mw(N_H(Y_0)) \geq |Y_0|</math> or <math>w(N_H(Y_0)) \geq 2 |Y_0| - 1</math>

Then, Шаблон:Mvar admits a Шаблон:Mvar-perfect matching.[7]Шаблон:Rp

In simple graphs

In a bipartite simple graph, the neighborhood-hypergraph contains just singletons - a singleton for every neighbor of Шаблон:Math. Since singletons do not intersect, the entire set of neighbors Шаблон:Math is a matching, and its only pinning-set is the set Шаблон:Math itself, i.e., the matching-width of Шаблон:Math is Шаблон:Math, and its width is the same:

<math>w(N_H(Y_0)) = mw(N_H(Y_0)) = |N_H(Y_0)|. </math>

Thus, both the above conditions are equivalent to Hall's marriage condition.

Examples

We consider several bipartite graphs with Шаблон:Math and Шаблон:Math The Aharoni–Haxell condition trivially holds for the empty set. It holds for subsets of size 1 if and only if each vertex in Шаблон:Mvar is contained in at least one edge, which is easy to check. It remains to check the subset Шаблон:Mvar itself.

  1. Шаблон:Math Here Шаблон:Math Its matching-width is at least 2, since it contains a matching of size 2, e.g. Шаблон:Math which cannot be pinned by any single edge from Шаблон:Math. Indeed, H admits a Шаблон:Mvar-perfect matching, e.g. Шаблон:Math
  2. Шаблон:Math Here Шаблон:Math Its matching-width is 1: it contains a matching of size 2, e.g. Шаблон:Math but this matching can be pinned by a single edge, e.g. Шаблон:Math The other matching of size 2 is Шаблон:Math but it too can be pinned by the single edge Шаблон:Math While Шаблон:Math is larger than in example 1, its matching-width is smaller - in particular, it is less than Шаблон:Math. Hence, the Aharoni–Haxell sufficient condition is not satisfied. Indeed, Шаблон:Mvar does not admit a Шаблон:Mvar-perfect matching.
  3. Шаблон:Math Here, as in the previous example, Шаблон:Math so the Aharoni–Haxell sufficient condition is violated. The width of Шаблон:Math is 2, since it is pinned e.g. by the set Шаблон:Math so Meshulam's weaker condition is violated too. However, this Шаблон:Mvar does admit a Шаблон:Mvar-perfect matching, e.g. Шаблон:Math which shows that these conditions are not necessary.

Set-family formulation

Consider a bipartite hypergraph Шаблон:Math where Шаблон:Math The Hall-type theorems do not care about the set Шаблон:Mvar itself - they only care about the neighbors of elements of Шаблон:Mvar. Therefore Шаблон:Mvar can be represented as a collection of families of sets Шаблон:Math where for each Шаблон:Mvar in Шаблон:Math, Шаблон:Math the set-family of neighbors of Шаблон:Mvar. For every subset Шаблон:Math of Шаблон:Mvar, the set-family Шаблон:Math is the union of the set-families Шаблон:Mvar for Шаблон:Mvar in Шаблон:Math. A perfect matching in Шаблон:Mvar is a set-family of size Шаблон:Mvar, where for each Шаблон:Mvar in Шаблон:Math, the set-family Шаблон:Mvar is represented by a set Шаблон:Mvar in Шаблон:Mvar, and the representative sets Шаблон:Mvar are pairwise-disjoint.

In this terminology, the Aharoni–Haxell theorem can be stated as follows.

Let Шаблон:Math be a collection of families of sets. For every sub-collection Шаблон:Mvar of Шаблон:Mvar, consider the set-family Шаблон:Math - the union of all the Шаблон:Mvar in Шаблон:Mvar. Suppose that, for every sub-collection Шаблон:Mvar of Шаблон:Mvar, this Шаблон:Math contains a matching Шаблон:Math such that at least Шаблон:Math disjoint subsets from Шаблон:Math are required for pinning Шаблон:Math. Then Шаблон:Mvar admits a system of disjoint representatives.

Necessary and sufficient condition

Let Шаблон:Math be a bipartite hypergraph. The following are equivalent:[6]Шаблон:Rp

In set-family formulation: let Шаблон:Math be a collection of families of sets. The following are equivalent:

Examples

Consider example #3 above: Шаблон:Math Шаблон:Math Шаблон:Math Шаблон:Math Since it admits a Шаблон:Mvar-perfect matching, it must satisfy the necessary condition. Indeed, consider the following assignment to subsets of Шаблон:Mvar:

In the sufficient condition pinning Шаблон:Math required at least two edges from Шаблон:Math it did not hold.

But in the necessary condition, pinning Шаблон:Math required at least two edges from Шаблон:Math it does hold.

Hence, the necessary+sufficient condition is satisfied.

Proof

The proof is topological and uses Sperner's lemma. Interestingly, it implies a new topological proof for the original Hall theorem.[13]

First, assume that no two vertices in Шаблон:Mvar have exactly the same neighbor (it is without loss of generality, since for each element Шаблон:Mvar of Шаблон:Mvar, one can add a dummy vertex to all neighbors of Шаблон:Mvar).

Let Шаблон:Math They consider an Шаблон:Mvar-vertex simplex, and prove that it admits a triangulation Шаблон:Mvar with some special properties that they call economically-hierarchic triangulation. Then they label each vertex of Шаблон:Mvar with a hyperedge from Шаблон:Math in the following way:

Their sufficient condition implies that such a labeling exists. Then, they color each vertex Шаблон:Mvar of Шаблон:Mvar with a color Шаблон:Mvar such that the hyperedge assigned to Шаблон:Mvar is a neighbor of Шаблон:Mvar.

Conditions (a) and (b) guarantee that this coloring satisfies Sperner's boundary condition. Therefore, a fully-labeled simplex exists. In this simplex there are Шаблон:Mvar hyperedges, each of which is a neighbor of a dif and only iferent element of Шаблон:Mvar, and so they must be disjoint. This is the desired Шаблон:Mvar-perfect matching.

Extensions

The Aharoni–Haxell theorem has a deficiency version. It is used to prove Ryser's conjecture for Шаблон:Math.[12]

Meshulam's conditions - the topological Hall theorems

In abstract simplicial complexes

Let Шаблон:Mvar be a set of vertices. Let Шаблон:Mvar be an abstract simplicial complex on Шаблон:Mvar. Let Шаблон:Mvar (for Шаблон:Mvar in Шаблон:Mvar) be subsets of Шаблон:Mvar. A Шаблон:Mvartransversal is a set in Шаблон:Mvar (an element of Шаблон:Mvar) whose intersection with each Шаблон:Mvar contains exactly one vertex. For every subset Шаблон:Math of Шаблон:Mvar, let

<math>V_{Y_0} := \bigcup_{y\in Y_0} V_y.</math>

Suppose that, for every subset Шаблон:Math of Шаблон:Mvar, the homological connectivity plus 2 of the sub-complex induced by <math>V_{Y_0}</math> is at least Шаблон:Math, that is:

<math>\eta_H(C[V_{Y_0}]) \geq |Y_0|.</math>

Then there exists a Шаблон:Mvartransversal. That is: there is a set in Шаблон:Mvar that intersects each Шаблон:Mvar by exactly one element.[14] This theorem has a deficiency version.[15] If, for every subset Шаблон:Math of Шаблон:Mvar:

<math>\eta_H(C[V_{Y_0}]) \geq |Y_0|-d,</math>

then there exists a partial Шаблон:Mvar-transversal, that intersects some Шаблон:Math sets by 1 element, and the rest by at most 1 element. More generally, if Шаблон:Mvar is a function on positive integers satisfying Шаблон:Math, and for every subset Шаблон:Math of Шаблон:Mvar:

<math>\eta_H(C[V_{Y_0}]) \geq g(|Y_0|),</math>

then there is a set in Шаблон:Mvar that intersects at least Шаблон:Math of the Шаблон:Mvar by at one element, and the others by at most one element.

Meshulam's game

Using the above theorem requires some lower bounds on homological connectivity. One such lower bound is given by Meshulam's game. This is a game played by two players on a graph. One player - CON - wants to prove that the graph has a high homological connectivity. The other player - NON - wants to prove otherwise. CON offers edges to NON one by one; NON can either disconnect an edge, or explode it; an explosion deletes the edge endpoints and all their neighbors. CON's score is the number of explosions when all vertices are gone, or infinity if some isolated vertices remain. The value of the game on a given graph Шаблон:Mvar (the score of CON when both players play optimally) is denoted by Шаблон:Math. This number can be used to get a lower bound on the homological connectivity of the independence complex of Шаблон:Mvar, denoted Шаблон:Tmath:

<math>\eta_H(\mathcal{I}(G)) \geq \Psi(G).</math>

Therefore, the above theorem implies the following. Let Шаблон:Mvar be a set of vertices. Let Шаблон:Mvar be a graph on Шаблон:Mvar. Suppose that, for every subset Шаблон:Math of Шаблон:Mvar:

<math>\Psi(G[V_{Y_0}]) \geq |Y_0|.</math>

Then there is an independent set in Шаблон:Mvar, that intersects each Шаблон:Mvar by exactly one element.

In simple bipartite graphs

Let Шаблон:Mvar be a bipartite graph with parts Шаблон:Mvar and Шаблон:Mvar. Let Шаблон:Mvar be the set of edges of Шаблон:Mvar. Let Шаблон:Math the line graph of Шаблон:Mvar. Then, the independence complex Шаблон:Tmath is equal to the matching complex of H, denoted Шаблон:Tmath. It is a simplicial complex on the edges of Шаблон:Mvar, whose elements are all the matchings on Шаблон:Mvar. For each vertex Шаблон:Mvar in Шаблон:Mvar, let Шаблон:Math be set of edges adjacent to Шаблон:Mvar (note that Шаблон:Math is a subset of Шаблон:Mvar). Then, for every subset Шаблон:Math of Шаблон:Mvar, the induced subgraph <math>G[V_{Y_0}]</math> contains a clique for every neighbor of Шаблон:Math (all edges adjacent to Шаблон:Math , that meet at the same vertex of Шаблон:Mvar, form a clique in the line-graph). So there are Шаблон:Math disjoint cliques. Therefore, when Meshulam's game is played, NON needs Шаблон:Math explosions to destroy all of Шаблон:Math, so Шаблон:Math. Thus, Meshulam's condition

<math>\Psi(G[V_{Y_0}]) \geq |Y_0|</math>

is equivalent to Hall's marriage condition. Here, the sets Шаблон:Mvar are pairwise-disjoint, so a Шаблон:Mvar-transversal contains a unique element from each Шаблон:Mvar, which is equivalent to a Шаблон:Mvar-saturating matching.

In matching complexes

Let Шаблон:Mvar be a bipartite hypergraph, and suppose Шаблон:Mvar is its matching complex Шаблон:Tmath. Let Шаблон:Mvar (for Шаблон:Mvar in Шаблон:Mvar) be sets of edges of Шаблон:Mvar. For every subset Шаблон:Math of Шаблон:Mvar, Шаблон:Tmath is the set of matchings in the sub-hypergraph:

<math>\bigcup_{y\in Y_0} H_y.</math>

If, for every subset Шаблон:Math of Шаблон:Mvar:

<math>\eta_H(\mathcal{M}(H_{Y_0})) \geq |Y_0|</math>

Then there exists a matching that intersects each set Шаблон:Mvar exactly once (it is also called a rainbow matching, since each Шаблон:Mvar can be treated as a color).

This is true, in particular, if we define Шаблон:Mvar as the set of edges of Шаблон:Mvar containing the vertex Шаблон:Mvar of Шаблон:Mvar. In this case, Шаблон:Tmath is equivalent to Шаблон:Math - the multi-hypergraph of neighbors of Шаблон:Math ("multi" - since each neighbor is allowed to appear several times for several different Шаблон:Mvar).

The matching complex of a hypergraph is exactly the independence complex of its line graph, denoted Шаблон:Math. This is a graph in which the vertices are the edges of Шаблон:Mvar, and two such vertices are connected iff their corresponding edges intersect in Шаблон:Mvar. Therefore, the above theorem implies:

<math>\eta_H(\mathcal{M}(H)) \geq \Psi(L(H))</math>

Combining the previous inequalities leads to the following condition.

Let Шаблон:Math be a bipartite hypergraph. Suppose that, for every subset Шаблон:Math of Шаблон:Mvar, the following condition holds:
<math>\Psi(L(N_H(Y_0))) \geq |Y_0|,</math>
where Шаблон:Math is considered a multi-hypergraph (i.e., it may contain the same hyperedge several times, if it is a neighbor of several different elements of Шаблон:Math). Then, Шаблон:Mvar admits a Шаблон:Mvar-perfect matching.[14]

Examples

We consider several bipartite hypergraphs with Шаблон:Math and Шаблон:Math The Meshulam condition trivially holds for the empty set. It holds for subsets of size 1 iff the neighbor-graph of each vertex in Шаблон:Mvar is non-empty (so it requires at least one explosion to destroy), which is easy to check. It remains to check the subset Шаблон:Mvar itself. s

  1. Шаблон:Math Here Шаблон:Math The graph Шаблон:Math has three vertices: Шаблон:Math Only the last two are connected; the vertex Aa is isolated. Hence, Шаблон:Math. Indeed, Шаблон:Mvar admits a Шаблон:Mvar-perfect matching, e.g. Шаблон:Math
  2. H = { {1,A,a}; {1,B,b}; {2,A,b}, {2,B,a} }. Here Шаблон:Math has four vertices: Шаблон:Math and four edges: Шаблон:Math For any edge that CON offers, NON can explode it and destroy all vertices. Hence, Шаблон:Math. Indeed, Шаблон:Mvar does not admit a Шаблон:Mvar-perfect matching.
  3. Шаблон:Math Шаблон:Math Шаблон:Math Шаблон:Math Here Шаблон:Math is the same as in the previous example, so Meshulam's sufficient condition is violated. However, this Шаблон:Mvar does admit a Шаблон:Mvar-perfect matching, e.g. Шаблон:Math which shows that this condition is not necessary.

No necessary-and-sufficient condition using Шаблон:Math is known.

More conditions from rainbow matchings

Шаблон:See also A rainbow matching is a matching in a simple graph, in which each edge has a different "color". By treating the colors as vertices in the set Шаблон:Mvar, one can see that a rainbow matching is in fact a matching in a bipartite hypergraph. Thus, several sufficient conditions for the existence of a large rainbow matching can be translated to conditions for the existence of a large matching in a hypergraph.

The following results pertain to tripartite hypergraphs in which each of the 3 parts contains exactly Шаблон:Mvar vertices, the degree of each vertex is exactly Шаблон:Mvar, and the set of neighbors of every vertex is a matching (henceforth "Шаблон:Mvar-tripartite-hypergraph"):

The following results pertain to more general bipartite hypergraphs:

Conforti-Cornuejols-Kapoor-Vuskovic condition: Balanced hypergraphs

A balanced hypergraph is an alternative generalization of a bipartite graph: it is a hypergraph in which every odd cycle Шаблон:Mvar of Шаблон:Mvar has an edge containing at least three vertices of Шаблон:Mvar.

Let Шаблон:Math be a balanced hypergraph. The following are equivalent:[24][25]

In simple graphs

A simple graph is bipartite iff it is balanced (it contains no odd cycles and no edges with three vertices).

Let Шаблон:Math for all edges Шаблон:Mvar in Шаблон:Mvar" means that Шаблон:Math contains all the neighbors of vertices of Шаблон:Math Hence, the CCKV condition becomes:

"If a subset Шаблон:Math of Шаблон:Mvar contains the set Шаблон:Math, then Шаблон:Math".

This is equivalent to Hall's condition.

See also

References

  1. ↑ 1,0 1,1 1,2 Шаблон:Cite journal
  2. ↑ 2,0 2,1 Шаблон:Cite book
  3. ↑ 3,0 3,1 Шаблон:Cite journal
  4. ↑ 4,0 4,1 4,2 Шаблон:Cite journal
  5. ↑ 5,0 5,1 Шаблон:Cite journal
  6. ↑ 6,0 6,1 6,2 6,3 6,4 Шаблон:Cite journal
  7. ↑ 7,0 7,1 7,2 Шаблон:Cite journal
  8. ↑ Шаблон:Citation
  9. ↑ Шаблон:Cite journal
  10. ↑ Шаблон:Cite journal
  11. ↑ Шаблон:Citation
  12. ↑ 12,0 12,1 Шаблон:Cite journal
  13. ↑ Шаблон:Cite web
  14. ↑ 14,0 14,1 Шаблон:Cite journal
  15. ↑ Шаблон:Cite arXiv
  16. ↑ Шаблон:Cite journal
  17. ↑ Шаблон:Cite journal
  18. ↑ Шаблон:Cite journal
  19. ↑ Шаблон:Cite journal
  20. ↑ Шаблон:Cite arXiv
  21. ↑ 21,0 21,1 Шаблон:Cite journal
  22. ↑ Шаблон:Cite journal
  23. ↑ 23,0 23,1 Шаблон:Cite journal
  24. ↑ Шаблон:Cite journal
  25. ↑ Шаблон:Cite journal
Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

Источник — http://wikihandbk.com/ruwiki/index.php?title=Английская_Википедия:Hall-type_theorems_for_hypergraphs&oldid=15113920