Such theorems were proved by Ofra Kessler,[1][2] Ron Aharoni,[3][4] Penny Haxell,[5][6] Roy Meshulam,[7] and others.
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.
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.
Hall's condition requires that, for each subset Y0 of Y, the set of neighbors of Y0 is sufficiently large.
Thus, to guarantee a perfect matching, a stronger condition is needed.
Suppose that, for every subset Y0 of Y, the following inequality holds: In words: the neighborhood-hypergraph of Y0 admits a matching larger than (r – 1) (|Y0| – 1).
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.
[4] Later it was proved[4] that, if the above condition holds, then H admits a Y-perfect fractional matching, i.e., ν*(H) = |Y|.
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.
Suppose that, for every subset Y0 of Y, the following inequality holds: In words: the neighborhood-hypergraph of Y0 has no transversal of size (2r – 3)(Y0 – 1) or less.
However, every subset Y0 of Y satisfies the following inequality: It is only slightly weaker (by 1) than required by Haxell's theorem.
However, Chidambaram Annamalai proved that a perfect matching can be found efficiently under a slightly stronger condition.
[8] 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 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.
[9][10][11] We say that a set K of edges pins another set F of edges if every edge in F intersects some edge in K.[6] The width of a hypergraph H = (V, E), denoted w(H), is the smallest size of a subset of E that pins E.[7] 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.[12] 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.
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.
Therefore H can be represented as a collection of families of sets {H1, …, Hm}, where for each i in [m], Hi := NH({i}) = the set-family of neighbors of i.
Suppose that, for every sub-collection B of A, this ∪ B contains a matching M(B) such that at least |B| disjoint subsets from ∪ B are required for pinning M(B).
The following are equivalent:[6]: Theorem 4.1 In set-family formulation: let A = {H1, …, Hm} be a collection of families of sets.
Indeed, consider the following assignment to subsets of Y: In the sufficient condition pinning M({1,2}) required at least two edges from NH(Y) = { {A,a}, {B,b}, {A,b}, {B,a} }; it did not hold.
Interestingly, it implies a new topological proof for the original Hall theorem.
In this simplex there are m hyperedges, each of which is a neighbor of a dif and only iferent element of Y, and so they must be disjoint.
One player - CON - wants to prove that the graph has a high homological connectivity.
The value of the game on a given graph G (the score of CON when both players play optimally) is denoted by Ψ(G).
This number can be used to get a lower bound on the homological connectivity of the independence complex of G, denoted
Let G be a graph on V. Suppose that, for every subset Y0 of Y: Then there is an independent set in G, that intersects each Vy by exactly one element.
This is true, in particular, if we define Hy as the set of edges of H containing the vertex y of Y.
This is a graph in which the vertices are the edges of H, and two such vertices are connected iff their corresponding edges intersect in H. Therefore, the above theorem implies: Combining the previous inequalities leads to the following condition.
It holds for subsets of size 1 iff the neighbor-graph of each vertex in Y is non-empty (so it requires at least one explosion to destroy), which is easy to check.
The following are equivalent:[24][25] A simple graph is bipartite iff it is balanced (it contains no odd cycles and no edges with three vertices).