Generalizations in graph theory
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 ("X" + "Y", "E") 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 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, 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 ("V", "E") with "V" = {1,2,3,4,5,6} and "E" = { {1,2,3}, {1,2,4}, {1,3,4}, {5,2}, {5,3,4,6} } is bipartite with "Y" = {1,5} and "X" = {2,3,4,6}.
2. Perfect matching: A matching in a hypergraph "H" = ("V", "E") 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 . A matching is called "Y-perfect" (or "Y-saturating") if its size is exactly . 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" = ("X" + "Y", "E") and a subset "Y"0 of Y, the neighbors of "Y"0 are the subsets of X that share hyperedges with vertices of "Y"0. Formally: 
formula_1
For example, in the hypergraph from point 1, we have: N"H"({1}) = { {2,3}, {2,4}, {3,4} } and N"H"({5}) = { {2}, {3,4,6} } and N"H"({1,5}) = { {2,3}, {2,4}, {3,4}, {2}, {3,4,6} }. 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 "Y"0. 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 "Y"0.
Since N"H"("Y"0) contains only subsets of X, one can define a hypergraph in which the vertex set is X and the edge set is N"H"("Y"0). We call it the neighborhood-hypergraph of "Y"0 and denote it:
formula_2 
Note that, if H is a simple bipartite graph, the neighborhood-hypergraph of every "Y"0 contains just the neighbors of "Y"0 in X, each of which with a self-loop.
Insufficiency of Hall's condition.
Hall's condition requires that, for each subset "Y"0 of Y, the set of neighbors of "Y"0 is sufficiently large. With hypergraphs this condition is insufficient. For example, consider the tripartite hypergraph with edges:{ {1, a, A}, {2, a, B} }Let "Y" = {1,2}. Every vertex in Y has a neighbor, and Y itself has two neighbors: N"H"("Y") = { {a,A}, {a,B} }. But there is no Y-perfect matching since both edges overlap.
One could try to fix it by requiring that N"H"("Y"0) contain at least "disjoint" edges, rather than just edges. In other words: "HH"("Y"0) should contain a "matching" of size at least . The largest size of a matching in a hypergraph H is called its matching number and denoted by "ν"("H") (thus H admits a Y-perfect matching if and only if "ν"("H") = |"Y"|). 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 "Y" = {1,2}. Again every vertex in Y has a neighbor, and Y itself has four neighbors: N"H"("Y") = { {a,A}, {a,B}, {b, A}, {b, B} }. Moreover, "ν"("HH"("Y")) = 2 since "HH"("Y") admits a matching of size 2, e.g. { {a,A}, {b,B} } or { {a,B}, {b,A} }. 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" = ("X" + "Y", "E") be a bipartite hypergraph (as defined in 1. above), in which the size of every hyperedge is exactly r, for some integer "r" ; 1. Suppose that, for every subset "Y"0 of Y, the following inequality holds:
formula_3
In words: the neighborhood-hypergraph of "Y"0 admits a matching larger than ("r" – 1) (|"Y"0| – 1). Then H admits a Y-perfect matching (as defined in 2. above).
This was first conjectured by Aharoni. It was proved with Ofra Kessler for bipartite hypergraphs in which 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:
formula_4
Moreover, the neighborhood-hypergraph (as defined in 3. above) contains just singletons - a singleton for every neighbor of "Y"0. Since singletons do not intersect, the entire set of singletons is a matching. Hence, "ν"("HH"("Y"0)) = |N"H"("Y"0)| = the number of neighbors of "Y"0. Thus, Aharoni's condition becomes, for every subset "Y"0 of Y:
formula_5
This is exactly Hall's marriage condition.
Tightness.
The following example shows that the factor ("r" – 1) cannot be improved. Choose some integer "m" ; 1. Let "H" = ("X" + "Y", "E") be the following r-uniform bipartite hypergraph:
Note that edge i in Em meets all edges in Ei.
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 "Y"0 of Y satisfies the following inequality
formula_8
since "HH"("Y"0 \ {"m"}) contains at least ("r" – 1) ⋅ (|"Y"0| – 1) hyperedges, and they are all disjoint.
Fractional matchings.
The largest size of a "fractional matching" in H is denoted by "ν"*("H"). Clearly "ν"*("H") ≥ "ν"("H"). Suppose that, for every subset "Y"0 of Y, the following weaker inequality holds:
formula_9
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., "ν"*("H") = |"Y"|. This is weaker than having a Y-perfect matching, which is equivalent to "ν"("H") = |"Y"|.
Haxell's condition: smallest transversal.
A "transversal" (also called "vertex-cover" or "hitting-set") in a hypergraph H = ("V", "E") 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 "τ"("H").
Let "H" = ("X" + "Y", "E") 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 "Y"0 of Y, the following inequality holds:
formula_10
In words: the neighborhood-hypergraph of "Y"0 has no transversal of size (2"r" – 3)("Y"0 – 1) or less.
Then, H admits a Y-perfect matching (as defined in 2. above).
In simple graphs.
For a bipartite simple graph "r" = 2 so 2"r" – 3 = 1, and Haxell's condition becomes:
formula_11
Moreover, the neighborhood-hypergraph (as defined in 3. above) contains just singletons - a singleton for every neighbor of "Y"0. In a hypergraph of singletons, a transversal must contain all vertices. Hence, "τ"("HH"("Y"0)) = |"N""H"("Y"0)| = the number of neighbors of "Y"0. Thus, Haxell's condition becomes, for every subset "Y"0 of Y:
formula_5
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 (2"r" – 3) cannot be improved. Let "H" = ("X" + "Y", "E") 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 "Y"0 of Y satisfies the following inequality:
formula_19
It is only slightly weaker (by 1) than required by Haxell's theorem. To verify this, it is sufficient to check the subset "Y"0 = "Y", since it is the only subset for which the right-hand side is larger than 0. The neighborhood-hypergraph of Y is ("X", "E"00 ∪ "E"11) where:
formula_20
formula_21
for formula_18
One can visualize the vertices of X as arranged on an ("r" – 1) × ("r" – 1) grid. The hyperedges of "E"00 are the "r" – 1 rows. The hyperedges of "E"11 are the ("r" – 1)"r"-1 selections of a single element in each row and each column. To cover the hyperedges of "E"10 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 (i.e., "v""i"1 for each i in {1, …, "r" – 1}). Now, since "E"11 contains all columns, we need at least "r" – 2 additional vertices - one vertex for each column {2, …, "r"}. All in all, each transversal requires at least 2"r" – 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 "r" ≥ 2 and "ε" ; 0, there exists an algorithm that finds a Y-perfect matching in every r-uniform bipartite hypergraph satisfying, for every subset "Y"0 of Y:
formula_23
In fact, in any r-uniform hypergraph, the algorithm finds either a Y-perfect matching, or a subset "Y"0 violating the above inequality.
The algorithm runs in time polynomial in the size of H, but exponential in r and .
It is an open question whether there exists an algorithm with run-time polynomial in either r or (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 K of edges "pins" another set F of edges if every edge in F intersects some edge in K. The "width" of a hypergraph "H" = ("V", "E"), denoted "w"("H"), is the smallest size of a subset of E that pins E. The "matching width" of a hypergraph H, denoted "mw"("H"), is the maximum, over all matchings M in H, of the minimum size of a subset of E that pins M. Since E contains all matchings in E, the width of H is obviously at least as large as the matching-width of H.
Aharoni and Haxell proved the following condition:Let "H" = ("X" + "Y", "E") be a bipartite hypergraph. Suppose that, for every subset "Y"0 of Y, the following inequality holds:formula_24[in other words: "NH"("Y"0) contains a matching M("Y"0) such that at least disjoint edges from "NH"("Y"0) are required for pinning M("Y"0)]. Then, H admits a Y-perfect matching.They later extended this condition in several ways, which were later extended by Meshulam as follows:Let "H" = ("X" + "Y", "E") be a bipartite hypergraph. Suppose that, for every subset "Y"0 of Y, at least one of the following conditions hold:formula_24 or
formula_26 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 "Y"0. Since singletons do not intersect, the entire set of neighbors "NH"("Y"0) is a matching, and its only pinning-set is the set "NH"("Y"0) itself, i.e., the matching-width of "NH"("Y"0) is , and its width is the same: 
formula_27
Thus, both the above conditions are equivalent to Hall's marriage condition.
Examples.
We consider several bipartite graphs with "Y" = {1, 2} and "X" = {A, B; a, b, c}. The Aharoni–Haxell condition trivially holds for the empty set. It holds for subsets of size 1 if and only if each vertex in Y is contained in at least one edge, which is easy to check. It remains to check the subset Y itself.
Set-family formulation.
Consider a bipartite hypergraph "H" = ("X" + "Y", "E") where "Y" = {1, …, "m"}. The Hall-type theorems do not care about the set Y itself - they only care about the neighbors of elements of Y.