Hall-type theorems for hypergraphs


In combinatorics, Hall-type theorems for hypergraphs are several generalization of Hall's marriage theorem from graphs to hypergraphs. Such theorems were proved by Penny Haxell, Ron Aharoni, Ofra Kessler and others.

Preliminaries

Hall's marriage theorem provides a condition guaranteeing that a bipartite graph admits a perfect matching, or - more generally - a matching that saturates all vertices of Y. The condition involves the number of neighbors of subsets of Y. Generalizing Hall's theorem to hypergraphs requires a generalizaion of the concepts of bipartiteness, perfect matching, and neighbors.
1. Bipartiteness: The notion of a bipartiteness can be extended to hypergraphs in many ways. 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, V can be partitioned into two sets X and Y, such that each hyperedge contains exactly one vertex of Y. A bipartite graph is a special case in which each edge contains exactly one vertex of Y and also exactly one vertex of X; in a bipartite hypergraph, each hyperedge contains exactly one vertex of Y but may contain zero or more vertices of X. For example, the hypergraph with V = and E = is bipartite with Y = and X =.
2. Perfect matching: A matching in a hypergraph H = is a subset F of E, such that every two hyperedges of F are disjoint. If H is bipartite with parts X and Y, then the size of each matching is obviously at most |Y|. A matching is called Y-perfect if its size is exactly |Y|. In other words: every vertex of Y appears in exactly one hyperedge of M. This definition reduces to the standard definition of a Y-perfect matching in a bipartite graph.
3. Neighbors: Given a bipartite hypergraph H = and a subset Y0 of Y, the neighbors of Y0 are the subsets of X that share hyperedges with vertices of Y0. Formally: . For example, in the hypergraph from point 1, we have: NH = and NH = and NH =. Note that, in a bipartite graph, each neighbor is a singleton - the neighbors are just the vertices of X that are adjacent to one or more vertices of Y0. In a bipartite hypergraph, each neighbor is a set - the neighbors are the subsets of X that are "adjacent" to one or more vertices of Y0.
Since NH contains only subsets of X, one can define a hypergraph in which the vertex set is X and the edge set is NH. We call it the neighborhood-hypergraph of Y0 and denote it by:. Note that, if H is a simple bipartite graph, the neighborhood-hypergraph of every Y0 contains just the neighbors of Y0 in X, each of which with a self-loop.

Insufficiency of Hall's condition

Hall's condition requires that, for each subset Y0 of Y, the set of neighbors of Y0 is sufficiently large. WIth hypergraphs this condition is insufficient. For example, consider the tripartite hypergraph with edges:
Let Y =. Every vertex in Y has a neighbor, and Y itself has two neighbors: NH =. But there is no Y-perfect matching since both edges overlap.
One could try to fix it by requiring that NH contain at least |Y0| disjoint edges, rather than just |Y0| edges. In other words: HH should contain a matching of size at least |Y0|. The largest size of a matching in a hypergraph H is called its matching number and denoted by . However, this fix is insufficient, as shown by the following tripartite hypergraph:
Let Y =. Again every vertex in Y has a neighbor, and Y itself has four neighbors: NH =. Moreover, since HH admits a matching of size 2, e.g. or. However, H does not admit a Y-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 H = be a bipartite hypergraph, in which the size of every hyperedge is exactly r, for some integer r > 1. Suppose that, for every subset Y0 of Y, the following inequality holds:
In words: the neighborhood-hypergraph of Y0 admits a matching larger than . Then H admits a Y-perfect matching .
This was first conjectured by Aharoni. It was proved with Ofra Kessler for bipartite hypergraphs in which |Y| ≤ 4 and for |Y| = 5. It was later proved for all r-uniform hypergraphs.

In simple graphs

For a bipartite simple graph r=2, and Aharoni's condition becomes. Moreover, the neighborhood-hypergraph contains just singletons - a singleton for every neighbor of Y0. Since singletons do not intersect, the entire set of singletons is a matching. Hence, the number of neighbors of Y0. Thus, Aharoni's condition becomes, for every subset Y0 of Y:

.
This is exactly Hall's marriage condition.

Tightness

The following example shows that the factor cannot be improved. Choose some integer m>1. Let H = be the following r-uniform bipartite hypergraph:
This H does not admit a Y-perfect matching, since every hyperedge that contains m intersects all hyperedges in Ei for some i < m.
However, every subset Y0 of Y satisfies the following inequality:
Since contains at least hyperedges, and they are all disjoint.

Fractional matchings

The largest size of a fractional matching in H is denoted by. Clearly. Suppose that, for every subset Y0 of Y, the following weaker inequality holds:
It was conjectured that in this case, too, H admits a Y-perfect matching. This stronger conjecture was proved for bipartite hypergraphs in which |Y| = 2.
Later it was proved that, if the above condition holds, then H admits a Y-perfect fractional matching, i.e., . This is weaker than having a Y-perfect matching, which is equivalent to.

Haxell's condition: smallest transversal

A transversal in a hypergraph H = is a subset U of V such that every hyperedge in E contains at least one vertex of U. The smallest size of a transversal in H is denoted by.
Let H = be a bipartite hypergraph in which the size of every hyperedge is at most r, for some integer r > 1. Suppose that, for every subset Y0 of Y, the following inequality holds:
In words: the neighborhood-hypergraph of Y0 has no transversal of size or less.
Then, H admits a Y-perfect matching.

In simple graphs

For a bipartite simple graph r=2 so 2r-3=1, and Haxell's condition becomes. Moreover, the neighborhood-hypergraph contains just singletons - a singleton for every neighbor of Y0. In a hypergraph of singletons, a transversal must contain all vertices. Hence, the number of neighbors of Y0. Thus, Haxell's condition becomes, for every subset Y0 of Y:

.
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 cannot be improved. Let H = be an r-uniform bipartite hypergraph with:
This H does not admit a Y-perfect matching, since every hyperedge that contains 0 intersects every hyperedge that contains 1.
However, every subset Y0 of Y satisfies the following inequality:
it is only slightly weaker than required by Haxell's theorem. To verify this, it is sufficient to check the subset Y0 = Y, since it is the only subset for which the right-hand side is larger than 0. The neighborhood-hypergraph of Y is where:
One can visualize the vertices of X as arranged on an times grid. The hyperedges of E00 are the r-1 rows. The hyperedges of E11 are the r-1 selections of a single element in each row and each column. To cover the hyperedges of E10 we need r - 1 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. Now, since E11 contains all columns, we need at least r - 2 additional vertices - one vertex for each column. All in all, each transversal requires at least 2r-3 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 and , there exists an algorithm that finds a Y-perfect matching in every r-uniform bipartite hypergraph satisfying, for every subset Y0 of Y:
In fact, in any r-uniform hypergraph, the algorithm finds either a Y-perfect matching, or a subset Y0 violating the above inequality.
The algorithm runs in time polynomial in the size of H, but exponential in r and 1/ε.
It is an open question whether there exists an algorithm with run-time polynomial in either r or 1/ε.
Similar algorithms have been applied for solving problems of fair item allocation, in particular the santa-claus problem.

Aharoni–Haxell conditions: smallest pinning set

A pinning set for a hypergraph H = is a subset F of subsets of V, such that every hyperedge in E meets at least one subset of F.
Let H = be a bipartite hypergraph. Suppose that, for every subset Y0 of Y, the neighbor-set NH contains a matching M such that at least |Y0| disjoint edges from NH are required for pinning M. Then, H admits a Y-perfect matching.

In simple graphs

In a bipartite simple graph, the neighborhood-hypergraph contains just singletons - a singleton for every neighbor of Y0. Since singletons do not intersect, the entire set of neighbors NH is a matching, and the only pinning-set is the set NH itself. Thus, the Aharoni–Haxell condition becomes, for every subset Y0 of Y:

.
This is exactly Hall's marriage condition.

Examples

We consider several bipartite graphs with Y = and X =. The Aharoni–Haxell condition trivially holds for the empty set. It holds for subsets of size 1 iff each vertex in Y is contained in at least one edge, which is easy to check. It remains to check the subset Y itself.
  1. H =. Here NH =. It contains a matching of size 2, e.g. , and this matching cannot be pinned by any single edge from NH. Indeed, H admits a Y-perfect matching, e.g..
  2. H =. Here NH =. It contains a matching of size 2, e.g. , but this matching can be pinned by a single edge, e.g.. The other matching of size 2 there is, but it too can be pinned by the single edge. While NH is larger than in example 1, its pinning number is smaller - in particular, it is less than |Y|. Hence, the Aharoni–Haxell sufficient condition is not satisfied. Indeed, H does not admit a Y-perfect matching.
  3. H =. Here, too, NH =, so the Aharoni–Haxell sufficient condition is not satisfied. However, this H does admit a Y-perfect matching, e.g., which shows that the condition is not necessary.

    Set-family formulation

Consider a bipartite hypergraph H = where Y =. The Hall-type theorems do not care about the set Y itself - they only care about the neighbors of elements of Y. Therefore H can be represented as a collection of families of sets, where for each i in , Hi := NH = the set-family of neighbors of i. For every subset Y0 of Y, the set-family NH is the union of the set-families Hi for i in Y0. A perfect matching in H is a set-family of size m, where for each i in , the set-family Hi is represented by a set Ri in Hi, and the representative sets Ri are pairwise-disjoint.
In this terminology, the Aharoni–Haxell theorem can be stated as follows.
Let A = be a collection of families of sets. For every sub-collection B of A, consider the set-family U B - the union of all the Hi in B. Suppose that, for every sub-collection B of A, this U B contains a matching M such that at least |B| disjoint subsets from U B are required for pinning M. Then A admits a system of disjoint representatives.

Necessary and sufficient condition

Let H = be a bipartite hypergraph. The following are equivalent:
In set-family formulation: let A = be a collection of families of sets. The following are equivalent:
Consider example #3 above: H =. Since it admits a Y-perfect matching, it must satisfy the necessary condition. Indeed, consider the following assignment to subsets of Y:
In the sufficient condition pinning M required at least two edges from NH = ; it did not hold.
But in the necessary condition, pinning M required at least two edges from M u M u M = ; 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 Y have exactly the same neighbor.
Let Y =. They consider an m-vertex simplex, and prove that it admits a triangulation T with some special properties that they call economically-hierarchic triangulation. Then they label each vertex of T with a hyperedge from NH in the following way:
Their sufficient condition implies that such a labeling exists. Then, they color each vertex v of T with a color i such that the hyperedge assigned to v is a neighbor of i.
Conditions and guarantee that this coloring satisfies Sperner's boundary condition. Therefore, a fully-labeled simplex exists. In this simplex there are m hyperedges, each of which is a neighbor of a different element of Y, and so they must be disjoint. This is the desired Y-perfect matching.

Extensions

The Aharoni–Haxell theorem has a deficiency version. It is used to prove Ryser's conjecture for r=3.

More conditions from rainbow matchings

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 Y, 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 n vertices, the degree of each vertex is exactly n, and the set of neighbors of every vertex is a matching :
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 C of H has an edge containing at least three vertices of C.
Let H = be a balanced hypergraph. The following are equivalent:
A simple graph is bipartite iff it is balanced.
Let G = be a bipartite graph. Let X0 be a subset of X and Y0 a subset of Y. The condition " for all edges e in E" means that X0 contains all the neigbors of vertices of Y0- Hence, the CCKV condition becomes:
"If a subset X0 of X contains the set NH, then |X0| ≥ |Y0|".
This is equivalent to Hall's condition.