Hall-type theorems for hypergraphs

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, Ron Aharoni, Penny Haxell, Roy Meshulam, and others.

Preliminaries

Hall's marriage theorem provides a condition guaranteeing that a bipartite graph Template:Math admits a perfect matching, or - more generally - a matching that saturates all vertices of Template:Mvar. The condition involves the number of neighbors of subsets of Template: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, Template:Mvar can be partitioned into two sets Template:Mvar and Template:Mvar, such that each hyperedge contains exactly one vertex of Template:Mvar. A bipartite graph is a special case in which each edge contains exactly one vertex of Template:Mvar and also exactly one vertex of Template:Mvar; in a bipartite hypergraph, each hyperedge contains exactly one vertex of Template:Mvar but may contain zero or more vertices of Template:Mvar. For example, the hypergraph Template:Math with Template:Math and Template:Math is bipartite with Template:Math and Template:Math

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

3. Neighbors: Given a bipartite hypergraph Template:Math and a subset Template:Math of Template:Mvar, the neighbors of Template:Math are the subsets of Template:Mvar that share hyperedges with vertices of Template:Math. Formally:

$N_H(Y_0):=\{X_0\subseteq X|\mathrm{\exists }{y}_0\in Y_0:\{y_0\}\cup X_0\in E\}.$

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

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

$H_H(Y_0):=(X,N_H(Y_0)).$

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

Insufficiency of Hall's condition

Hall's condition requires that, for each subset Template:Math of Template:Mvar, the set of neighbors of Template: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 Template:Math Every vertex in Template:Mvar has a neighbor, and Template:Mvar itself has two neighbors: Template:Math But there is no Template:Mvar-perfect matching since both edges overlap. One could try to fix it by requiring that Template:Math contain at least Template:Math disjoint edges, rather than just Template:Math edges. In other words: Template:Math should contain a matching of size at least Template:Math. The largest size of a matching in a hypergraph Template:Mvar is called its matching number and denoted by Template:Math (thus Template:Mvar admits a Template:Mvar-perfect matching if and only if Template: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 Template:Math Again every vertex in Template:Mvar has a neighbor, and Template:Mvar itself has four neighbors: Template:Math Moreover, Template:Math since Template:Math admits a matching of size 2, e.g. Template:Math However, H does not admit a Template: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 Template:Math be a bipartite hypergraph (as defined in 1. above), in which the size of every hyperedge is exactly Template:Mvar, for some integer Template:Math. Suppose that, for every subset Template:Math of Template:Mvar, the following inequality holds:

$\nu (N_H(Y_0))\ge (r-1)\cdot (|Y_0|-1)+1$

In words: the neighborhood-hypergraph of Template:Math admits a matching larger than Template:Math. Then Template:Mvar admits a Template:Mvar-perfect matching (as defined in 2. above).

This was first conjectured by Aharoni. It was proved with Ofra Kessler for bipartite hypergraphs in which Template:Math and for Template:Math. It was later proved for all Template:Mvar-uniform hypergraphs.Template:Rp

In simple graphs

For a bipartite simple graph Template:Math, and Aharoni's condition becomes:

$\nu (H_H(Y_0))\ge |Y_0|.$

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

$|N_H(Y_0)|\ge |Y_0|.$

This is exactly Hall's marriage condition.

Tightness

The following example shows that the factor Template:Math cannot be improved. Choose some integer Template:Math. Let Template:Math be the following Template:Mvar-uniform bipartite hypergraph:

• Template:Math
• Template:Mvar is the union of Template:Math (where Template:Mvar is the set of hyperedges containing vertex Template:Mvar), and:
  • For each Template:Mvar in Template:Math Template:Mvar contains Template:Math disjoint hyperedges of size Template:Mvar: $\{i,x_{i,1,1},\dots ,x_{i,1,r-1}\},\dots ,\{i,x_{i,r-1,1},\dots ,x_{i,r-1,r-1}\}.$
  • Template:Mvar contains Template:Math hyperedges of size Template:Mvar: $\{m,x_{1,1,1},\dots ,x_{1,r-1,r-1},\},\dots ,\{m,x_{m-1,1,1},\dots ,x_{m-1,r-1,1}\}$

Note that edge Template:Mvar in Template:Mvar meets all edges in Template:Mvar.

This Template:Mvar does not admit a Template:Mvar-perfect matching, since every hyperedge that contains Template:Mvar intersects all hyperedges in Template:Mvar for some Template:Math.

However, every subset Template:Math of Template:Mvar satisfies the following inequality

$\nu (H_H(Y_0))\ge (r-1)\cdot (|Y_0|-1)$

since Template:Math contains at least Template:Math hyperedges, and they are all disjoint.

Fractional matchings

The largest size of a fractional matching in Template:Mvar is denoted by Template:Math. Clearly Template:Math. Suppose that, for every subset Template:Math of Template:Mvar, the following weaker inequality holds:

${\nu }^{*}(H_H(Y_0))\ge (r-1)\cdot (|Y_0|-1)+1$

It was conjectured that in this case, too, Template:Mvar admits a Template:Mvar-perfect matching. This stronger conjecture was proved for bipartite hypergraphs in which Template:Math.

Later it was proved that, if the above condition holds, then Template:Mvar admits a Template:Mvar-perfect fractional matching, i.e., Template:Math. This is weaker than having a Template:Mvar-perfect matching, which is equivalent to Template:Math.

Haxell's condition: smallest transversal

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

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

$\tau (H_H(Y_0))\ge (2r-3)\cdot (|Y_0|-1)+1$

In words: the neighborhood-hypergraph of Template:Math has no transversal of size Template:Math or less.

Then, Template:Mvar admits a Template:Mvar-perfect matching (as defined in 2. above).Template:Rp

In simple graphs

For a bipartite simple graph Template:Math so Template:Math, and Haxell's condition becomes:

$\tau (H_H(Y_0))\ge |Y_0|.$

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

$|N_H(Y_0)|\ge |Y_0|.$

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 Template:Math cannot be improved. Let Template:Math be an Template:Mvar-uniform bipartite hypergraph with:

• $Y=\{0,1\}$
• $X=\{x_{ij}:1\le i,j\le r-1\}$ [so Template:Math].

• $E=E_0\cup E_1,$ where:
  • $E_0=\{\{0,x_{i1},\dots ,x_{i(r-1)}\}|1\le i\le r-1\}$
    [so Template:Math contains Template:Math hyperedges].
  • $E_1=\{\{1,x_{1j[1]},\dots ,x_{(r-1)j[r-1]}\}|1\le j[k]\le r-1$
    for $1\le k\le r-1\}$
    [so Template:Math contains Template:Math hyperedges].

This Template:Mvar does not admit a Template:Mvar-perfect matching, since every hyperedge that contains 0 intersects every hyperedge that contains 1.

However, every subset Template:Math of Template:Mvar satisfies the following inequality:

$\tau (H_H(Y_0))\ge (2r-3)\cdot (|Y_0|-1)$

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

$E_{00}=\{\{x_{i1},\dots ,x_{i(r-1)}\}|1\le i\le r-1\}$

$E_{11}=\{\{x_{1j[1]},\dots ,x_{(r-1)j[r-1]}\}|1\le j[k]\le r-1$

for $1\le k\le r-1\}$

One can visualize the vertices of Template:Mvar as arranged on an Template:Math grid. The hyperedges of Template:Math are the Template:Math rows. The hyperedges of Template:Math are the Template:Math selections of a single element in each row and each column. To cover the hyperedges of Template:Math we need Template: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., Template:Math for each Template:Mvar in Template:Math. Now, since Template:Math contains all columns, we need at least Template:Math additional vertices - one vertex for each column Template:Math All in all, each transversal requires at least Template: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.

For every fixed choice of Template:Math and Template:Math, there exists an algorithm that finds a Template:Mvar-perfect matching in every Template:Mvar-uniform bipartite hypergraph satisfying, for every subset Template:Math of Template:Mvar:

$\tau (H_H(Y_0))\ge (2r-3+ϵ)\cdot (|Y_0|-1)+1$

In fact, in any Template:Mvar-uniform hypergraph, the algorithm finds either a Template:Mvar-perfect matching, or a subset Template:Math violating the above inequality.

The algorithm runs in time polynomial in the size of Template:Mvar, but exponential in Template:Mvar and Template:Math.

It is an open question whether there exists an algorithm with run-time polynomial in either Template:Mvar or Template:Math (or both).

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

Aharoni–Haxell conditions: smallest pinning sets

We say that a set Template:Mvar of edges pins another set Template:Mvar of edges if every edge in Template:Mvar intersects some edge in Template:Mvar. The width of a hypergraph Template:Math, denoted Template:Math, is the smallest size of a subset of Template:Mvar that pins Template:Mvar. The matching width of a hypergraph Template:Mvar, denoted Template:Math, is the maximum, over all matchings Template:Mvar in Template:Mvar, of the minimum size of a subset of Template:Mvar that pins Template:Mvar. Since Template:Mvar contains all matchings in Template:Mvar, the width of H is obviously at least as large as the matching-width of Template:Mvar.

Aharoni and Haxell proved the following condition:

Let Template:Math be a bipartite hypergraph. Suppose that, for every subset Template:Math of Template:Mvar, the following inequality holds:

$mw(N_H(Y_0))\ge |Y_0|$

[in other words: Template:Math contains a matching Template:Math such that at least Template:Math disjoint edges from Template:Math are required for pinning Template:Math]. Then, Template:Mvar admits a Template:Mvar-perfect matching.Template:Rp

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

Let Template:Math be a bipartite hypergraph. Suppose that, for every subset Template:Math of Template:Mvar, at least one of the following conditions hold:

$mw(N_H(Y_0))\ge |Y_0|$

or

$w(N_H(Y_0))\ge 2|Y_0|-1$

Then, Template:Mvar admits a Template:Mvar-perfect matching.Template:Rp

In simple graphs

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

$w(N_H(Y_0))=mw(N_H(Y_0))=|N_H(Y_0)|.$

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

Examples

We consider several bipartite graphs with Template:Math and Template: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 Template:Mvar is contained in at least one edge, which is easy to check. It remains to check the subset Template:Mvar itself.

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

Set-family formulation

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

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

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

Necessary and sufficient condition

Let Template:Math be a bipartite hypergraph. The following are equivalent:Template:Rp

• Template:Mvar admits a Template:Mvar-perfect matching.
• There is an assignment of a matching Template:Math in Template:Math for every subset Template:Math of Template:Mvar, such that pinning Template:Math requires at least Template:Math disjoint edges from Template:Math is a subset of Template:Math

In set-family formulation: let Template:Math be a collection of families of sets. The following are equivalent:

• Template:Mvar admits a system of disjoint representatives;
• There is an assignment of a matching Template:Math in Template:Math for every sub-collection Template:Mvar of Template:Mvar, such that, for pinning Template:Math, at least Template:Math edges from Template:Math is a subcollection of Template:Math are required.

Examples

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

• Template:Math
• Template:Math
• Template:Math

In the sufficient condition pinning Template:Math required at least two edges from Template:Math it did not hold.

But in the necessary condition, pinning Template:Math required at least two edges from Template: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.

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

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

• (a) For each Template:Mvar in Template:Mvar, The main vertex Template:Mvar of the simplex is labeled with some hyperedge from the matching Template:Math.
• (b) Each vertex of Template:Mvar on a face spanned by a subset Template:Math of Template:Mvar, is labeled by some hyperedge from the matching Template:Math.
• (c) For each two adjacent vertices of Template:Mvar, their labels are either identical or disjoint.

Their sufficient condition implies that such a labeling exists. Then, they color each vertex Template:Mvar of Template:Mvar with a color Template:Mvar such that the hyperedge assigned to Template:Mvar is a neighbor of Template: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 Template:Mvar hyperedges, each of which is a neighbor of a dif and only iferent element of Template:Mvar, and so they must be disjoint. This is the desired Template:Mvar-perfect matching.

Extensions

The Aharoni–Haxell theorem has a deficiency version. It is used to prove Ryser's conjecture for Template:Math.

Meshulam's conditions - the topological Hall theorems

In abstract simplicial complexes

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

$V_{Y_0}:=\bigcup _{y\in Y_0}{V}_y.$

Suppose that, for every subset Template:Math of Template:Mvar, the homological connectivity plus 2 of the sub-complex induced by $V_{Y_0}$ is at least Template:Math, that is:

${\eta }_H(C[V_{Y_0}])\ge |Y_0|.$

Then there exists a Template:Mvartransversal. That is: there is a set in Template:Mvar that intersects each Template:Mvar by exactly one element. This theorem has a deficiency version. If, for every subset Template:Math of Template:Mvar:

${\eta }_H(C[V_{Y_0}])\ge |Y_0|-d,$

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

${\eta }_H(C[V_{Y_0}])\ge g(|Y_0|),$

then there is a set in Template:Mvar that intersects at least Template:Math of the Template: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 Template:Mvar (the score of CON when both players play optimally) is denoted by Template:Math. This number can be used to get a lower bound on the homological connectivity of the independence complex of Template:Mvar, denoted Template:Tmath:

${\eta }_H(ℐ(G))\ge \mathrm{\Psi }(G).$

Therefore, the above theorem implies the following. Let Template:Mvar be a set of vertices. Let Template:Mvar be a graph on Template:Mvar. Suppose that, for every subset Template:Math of Template:Mvar:

$\mathrm{\Psi }(G[V_{Y_0}])\ge |Y_0|.$

Then there is an independent set in Template:Mvar, that intersects each Template:Mvar by exactly one element.

In simple bipartite graphs

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

$\mathrm{\Psi }(G[V_{Y_0}])\ge |Y_0|$

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

In matching complexes

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

$\bigcup _{y\in Y_0}{H}_y.$

If, for every subset Template:Math of Template:Mvar:

${\eta }_H(ℳ(H_{Y_0}))\ge |Y_0|$

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

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

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

${\eta }_H(ℳ(H))\ge \mathrm{\Psi }(L(H))$

Combining the previous inequalities leads to the following condition.

Let Template:Math be a bipartite hypergraph. Suppose that, for every subset Template:Math of Template:Mvar, the following condition holds:

$\mathrm{\Psi }(L(N_H(Y_0)))\ge |Y_0|,$

where Template: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 Template:Math). Then, Template:Mvar admits a Template:Mvar-perfect matching.

Examples

We consider several bipartite hypergraphs with Template:Math and Template: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 Template:Mvar is non-empty (so it requires at least one explosion to destroy), which is easy to check. It remains to check the subset Template:Mvar itself. s

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

No necessary-and-sufficient condition using Template:Math is known.

More conditions from rainbow matchings

Template: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 Template: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 Template:Mvar vertices, the degree of each vertex is exactly Template:Mvar, and the set of neighbors of every vertex is a matching (henceforth "Template:Mvar-tripartite-hypergraph"):

• Every Template:Mvar-tripartite-hypergraph has a matching of size Template:Math.
• Every Template:Mvar-tripartite-hypergraph has a matching of size Template:Math.
• Every Template:Mvar-tripartite-hypergraph has a matching of size Template:Math.
• Every Template:Mvar-tripartite-hypergraph has a matching of size Template:Math.
• Every Template:Mvar-tripartite-hypergraph has a matching of size Template:Math. (Preprint)
• H. J. Ryser conjectured that, when Template:Mvar is odd, every Template:Mvar-tripartite-hypergraph has a matching of size Template:Mvar.
• S. K. Stein and Brualdi conjectured that, when Template:Mvar is even, every Template:Mvar-tripartite-hypergraph has a matching of size Template:Math. (it is known that a matching of size Template:Mvar might not exist in this case).
• A more general conjecture of Stein is that a matching of size Template:Math exists even without requiring that the set of neighbors of every vertex in Template:Mvar is a matching.

The following results pertain to more general bipartite hypergraphs:

• Any tripartite hypergraph Template:Math in which Template:Math, the degree of each vertex Template:Mvar in Template:Mvar is Template:Mvar, and the neighbor-set of Template:Mvar is a matching, has a matching of size Template:Mvar. The Template:Math is the best possible: if Template:Math, then the maximum matching may be of size Template:Mvar-1.
• Any bipartite hypergraph Template:Math in which Template:Math, the degree of each vertex y in Template:Mvar is Template:Mvar, and the neighbor-set of Template:Mvar is a matching, has a matching of size Template:Mvar. It is not known whether this is the best possible. For even Template:Mvar, it is only known that Template:Math is required; for odd Template:Mvar, it is only known that Template:Math is required.

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 Template:Mvar of Template:Mvar has an edge containing at least three vertices of Template:Mvar.

Let Template:Math be a balanced hypergraph. The following are equivalent:

• Template:Mvar admits a perfect matching (i.e., a matching in which each vertex is matched).
• For all disjoint vertex-sets Template:Math, Template:Math, if Template:Math, then there exists an edge Template:Mvar in Template:Mvar such that Template:Math (equivalently: if Template:Math for all edges Template:Mvar in Template:Mvar, then Template:Math).

In simple graphs

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

Let Template:Math for all edges Template:Mvar in Template:Mvar" means that Template:Math contains all the neighbors of vertices of Template:Math Hence, the CCKV condition becomes:

"If a subset Template:Math of Template:Mvar contains the set Template:Math, then Template:Math".

This is equivalent to Hall's condition.

See also

• Perfect matching in high-degree hypergraphs - presents other sufficient conditions for the existence of perfect matchings, which are based only on the degree of vertices.