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 |Y|. A matching is called Y-perfect (or Y-saturating) 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 = (X + Y, E) and a subset Y0 of Y, the neighbors of Y0 are the subsets of X that share hyperedges with vertices of Y0. Formally:
N H ( Y 0 ) := { X 0 ⊆ X | ∃ y 0 ∈ Y 0 : { y 0 } ∪ X 0 ∈ E } . {\displaystyle N_{H}(Y_{0}):=\{X_{0}\subseteq X~~|~~\exists y_{0}\in Y_{0}:~\{y_{0}\}\cup X_{0}\in E\}.}
For example, in the hypergraph from point 1, we have: NH({1}) = { {2,3}, {2,4}, {3,4} } and NH({5}) = { {2}, {3,4,6} } and NH({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 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(Y0) contains only subsets of X, one can define a hypergraph in which the vertex set is X and the edge set is NH(Y0). We call it the neighborhood-hypergraph of Y0 and denote it:
H H ( Y 0 ) := ( X , N H ( Y 0 ) ) . {\displaystyle H_{H}(Y_{0}):=(X,N_{H}(Y_{0})).}
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:{ {1, a, A}, {2, a, B} }Let Y = {1,2}. Every vertex in Y has a neighbor, and Y itself has two neighbors: NH(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 NH(Y0) contain at least |Y0| disjoint edges, rather than just |Y0| edges. In other words: HH(Y0) 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 ν(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: NH(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 Y0 of Y, the following inequality holds:
ν ( N H ( Y 0 ) ) ≥ ( r − 1 ) ⋅ ( | Y 0 | − 1 ) + 1 {\displaystyle \nu (N_{H}(Y_{0}))\geq (r-1)\cdot (|Y_{0}|-1)+1}
… excerpt ends here. Continue reading the full article.
