Hall-type theorems for hypergraphs

For a bipartite simple graph r = 2, and Aharoni's condition becomes:

${\displaystyle \nu (H_{H}(Y_{0}))\geq |Y_{0}|.}$

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

${\displaystyle |N_{H}(Y_{0})|\geq |Y_{0}|.}$

This is exactly Hall's marriage condition.

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:

• Y = {1, ..., m};
• E is the union of E₁, … , E_m (where E_i is the set of hyperedges containing vertex i), and:
  • For each i in {1, … , m – 1}, E_i contains r – 1 disjoint hyperedges of size r: ${\displaystyle \{i,x_{i,1,1},\ldots ,x_{i,1,r-1}\},\ldots ,\{i,x_{i,r-1,1},\ldots ,x_{i,r-1,r-1}\}.}$
  • E_m contains m – 1 hyperedges of size r: ${\displaystyle \{m,x_{1,1,1},\ldots ,x_{1,r-1,r-1},\},\ldots ,\{m,x_{m-1,1,1},\ldots ,x_{m-1,r-1,1}\}}$

Note that edge i in E_m meets all edges in E_i.

This H does not admit a Y-perfect matching, since every hyperedge that contains m intersects all hyperedges in E_i for some i < m.

However, every subset Y₀ of Y satisfies the following inequality

${\displaystyle \nu (H_{H}(Y_{0}))\geq (r-1)\cdot (|Y_{0}|-1)}$

since H_H(Y₀ \ {m}) contains at least (r – 1) ⋅ (|Y₀| – 1) hyperedges, and they are all disjoint.

The largest size of a fractional matching in H is denoted by ν*(H). Clearly ν*(H) ≥ ν(H). Suppose that, for every subset Y₀ of Y, the following weaker inequality holds:

${\displaystyle \nu ^{*}(H_{H}(Y_{0}))\geq (r-1)\cdot (|Y_{0}|-1)+1}$

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.[4]

Later it was proved[4] 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|.

For a bipartite simple graph r = 2 so 2r – 3 = 1, and Haxell's condition becomes:

${\displaystyle \tau (H_{H}(Y_{0}))\geq |Y_{0}|.}$

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

${\displaystyle |N_{H}(Y_{0})|\geq |Y_{0}|.}$

This is exactly Hall's marriage condition. Thus, Haxell's theorem implies Hall's marriage theorem for bipartite simple graphs.

The following example shows that the factor (2r – 3) cannot be improved. Let H = (X + Y, E) be an r-uniform bipartite hypergraph with:

• ${\displaystyle Y=\{0,1\}}$
• ${\displaystyle X=\{x_{ij}:1\leq i,j\leq r-1\}}$ [so |X| = (r – 1)²].

• ${\displaystyle E=E_{0}\cup E_{1},}$ where:
  • ${\displaystyle E_{0}=\{\{0,x_{i1},\ldots ,x_{i(r-1)}\}|1\leq i\leq r-1\}}$
    [so E₀ contains r – 1 hyperedges].
  • ${\displaystyle E_{1}=\{\{1,x_{1j[1]},\ldots ,x_{(r-1)j[r-1]}\}|1\leq j[k]\leq r-1}$
    for ${\displaystyle 1\leq k\leq r-1\}}$
    [so E₁ contains (r – 1)^r-1 hyperedges].

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₀ of Y satisfies the following inequality:

${\displaystyle \tau (H_{H}(Y_{0}))\geq (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 Y₀ = 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₀₀ ∪ E₁₁) where:

${\displaystyle E_{00}=\{\{x_{i1},\ldots ,x_{i(r-1)}\}|1\leq i\leq r-1\}}$

${\displaystyle E_{11}=\{\{x_{1j[1]},\ldots ,x_{(r-1)j[r-1]}\}|1\leq j[k]\leq r-1}$

for ${\displaystyle 1\leq k\leq r-1\}}$

One can visualize the vertices of X as arranged on an (r – 1) × (r – 1) grid. The hyperedges of E₀₀ are the r – 1 rows. The hyperedges of E₁₁ are the (r – 1)^r-1 selections of a single element in each row and each column. To cover the hyperedges of E₁₀ 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_i1 for each i in {1, …, r – 1}). Now, since E₁₁ 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 2r – 3 vertices.

Haxell's proof is not constructive. 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 Y₀ of Y:

${\displaystyle \tau (H_{H}(Y_{0}))\geq (2r-3+\epsilon )\cdot (|Y_{0}|-1)+1}$

In fact, in any r-uniform hypergraph, the algorithm finds either a Y-perfect matching, or a subset Y₀ 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⁄ε (or both).

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

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

${\displaystyle 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.

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.

1. H = { {1,A,a}; {2,B,b}; {2,B,c} }. Here N_H(Y) = { {A,a}, {B,b}, {B,c} }. Its matching-width is at least 2, since it contains a matching of size 2, e.g. { {A,a}, {B,b} }, which cannot be pinned by any single edge from N_H(Y₀). Indeed, H admits a Y-perfect matching, e.g. { {1,A,a}; {2,B,b} }.
2. H = { {1,A,a}; {1,B,b}; {2,A,b}, {2,B,a} }. Here N_H(Y) = { {A,a}, {B,b}, {A,b}, {B,a} }. Its matching-width is 1: it contains a matching of size 2, e.g. { {A,a}, {B,b} }, but this matching can be pinned by a single edge, e.g. {A,b}. The other matching of size 2 is { {A,b},{B,a} }, but it too can be pinned by the single edge {A,a}. While N_H(Y) is larger than in example 1, its matching-width 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 = { {1,A,a}, {1,A,b}; {1,B,a}, {1,B,b}; {2,A,a}, {2,A,b}; {2,B,a}, {2,B,b} }. Here, as in the previous example, N_H(Y) = { {A,a}, {B,b}, {A,b}, {B,a} }, so the Aharoni–Haxell sufficient condition is violated. The width of N_H(Y) is 2, since it is pinned e.g. by the set { {A,a}, {B,b} }, so Meshulam's weaker condition is violated too. However, this H does admit a Y-perfect matching, e.g. { {1,A,a}; {2,B,b} }, which shows that these conditions are not necessary.

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. Therefore H can be represented as a collection of families of sets {H₁, …, H_m}, where for each i in [m], H_i := N_H({i}) = the set-family of neighbors of i. For every subset Y₀ of Y, the set-family N_H(Y₀) is the union of the set-families H_i for i in Y₀. A perfect matching in H is a set-family of size m, where for each i in [m], the set-family H_i is represented by a set R_i in H_i, and the representative sets R_i are pairwise-disjoint.

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

Let A = {H₁, …, H_m} be a collection of families of sets. For every sub-collection B of A, consider the set-family ∪ B - the union of all the H_i in B. 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). Then A admits a system of disjoint representatives.

Let H = (X + Y, E) be a bipartite hypergraph. The following are equivalent:[6]^{: Theorem 4.1}

• H admits a Y-perfect matching.
• There is an assignment of a matching M(Y₀) in N_H(Y₀) for every subset Y₀ of Y, such that pinning M(Y₀) requires at least |₀| disjoint edges from ∪ {M(Y₁): Y₁ is a subset of Y₀}.

In set-family formulation: let A = {H₁, …, H_m} be a collection of families of sets. The following are equivalent:

• A admits a system of disjoint representatives;
• There is an assignment of a matching M(B in ∪ B for every sub-collection B of A, such that, for pinning M(B), at least |B| edges from ∪ {M(C): C is a subcollection of B} are required.

Consider example #3 above: H = { {1,A,a}, {1,A,b}; {1,B,a}, {1,B,b}; {2,A,a}, {2,A,b}; {2,B,a}, {2,B,b} }. Since it admits a Y-perfect matching, it must satisfy the necessary condition. Indeed, consider the following assignment to subsets of Y:

• M({1}) = {A,a}
• M({2}) = {B,b}
• M({1,2}) = { {A, a}, {B, b} }

In the sufficient condition pinning M({1,2}) required at least two edges from N_H(Y) = { {A,a}, {B,b}, {A,b}, {B,a} }; it did not hold.

But in the necessary condition, pinning M({1,2}) required at least two edges from M({1}) ∪ M({2}) ∪ M({1,2}) = { {A,a}, {B,b} }; it does hold.

Hence, the necessary+sufficient condition is satisfied.

The proof is topological and uses Sperner's lemma. Interestingly, it implies a new topological proof for the original Hall theorem.[13]

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

Let Y = {1, …, m}. 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 N_H(Y) in the following way:

• (a) For each i in Y, The main vertex i of the simplex is labeled with some hyperedge from the matching M({i}).
• (b) Each vertex of T on a face spanned by a subset Y₀ of Y, is labeled by some hyperedge from the matching M(Y₀).
• (c) For each two adjacent vertices of T, their labels are either identical or disjoint.

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 (a) and (b) 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 dif and only iferent element of Y, and so they must be disjoint. This is the desired Y-perfect matching.

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

Let V be a set of vertices. Let C be an abstract simplicial complex on V. Let V_y (for y in Y) be subsets of V. A C-V-transversal is a set in C (an element of C) whose intersection with each V_y contains exactly one vertex. For every subset Y₀ of Y, let

${\displaystyle V_{Y_{0}}:=\bigcup _{y\in Y_{0}}V_{y}.}$

Suppose that, for every subset Y₀ of Y, the homological connectivity plus 2 of the sub-complex induced by ${\displaystyle V_{Y_{0}}}$ is at least |Y₀|, that is:

${\displaystyle \eta _{H}(C[V_{Y_{0}}])\geq |Y_{0}|.}$

Then there exists a C-V-transversal. That is: there is a set in C that intersects each V_y by exactly one element.[14] This theorem has a deficiency version.[15] If, for every subset Y₀ of Y:

${\displaystyle \eta _{H}(C[V_{Y_{0}}])\geq |Y_{0}|-d,}$

then there exists a partial C-transversal, that intersects some |Y| – d sets by 1 element, and the rest by at most 1 element. More generally, if g is a function on positive integers satisfying g(z + 1) ≤ g(z) + 1, and for every subset Y₀ of Y:

${\displaystyle \eta _{H}(C[V_{Y_{0}}])\geq g(|Y_{0}|),}$

then there is a set in C that intersects at least g(|Y|) of the V_y by at one element, and the others by at most one element.

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 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 ${\displaystyle {\mathcal {I}}(G)}$:

${\displaystyle \eta _{H}({\mathcal {I}}(G))\geq \Psi (G).}$

Therefore, the above theorem implies the following. Let V be a set of vertices. Let G be a graph on V. Suppose that, for every subset Y₀ of Y:

${\displaystyle \Psi (G[V_{Y_{0}}])\geq |Y_{0}|.}$

Then there is an independent set in G, that intersects each V_y by exactly one element.

Let H be a bipartite graph with parts X and Y. Let V be the set of edges of H. Let G = L(H) = the line graph of H. Then, the independence complex ${\displaystyle {\mathcal {I}}(L(H))}$ is equal to the matching complex of H, denoted ${\displaystyle {\mathcal {M}}(H)}$. It is a simplicial complex on the edges of H, whose elements are all the matchings on H. For each vertex y in Y, let V_y be set of edges adjacent to y (note that V_y is a subset of V). Then, for every subset Y₀ of Y, the induced subgraph ${\displaystyle G[V_{Y_{0}}]}$ contains a clique for every neighbor of Y₀ (all edges adjacent to Y₀ , that meet at the same vertex of X, form a clique in the line-graph). So there are |N_H(Y₀)| disjoint cliques. Therefore, when Meshulam's game is played, NON needs |N_H(Y₀)| explosions to destroy all of L(N_H(Y₀)), so Ψ(L(N_H(Y₀)) = |N_H(Y₀)|. Thus, Meshulam's condition

${\displaystyle \Psi (G[V_{Y_{0}}])\geq |Y_{0}|}$

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

Let H be a bipartite hypergraph, and suppose C is its matching complex ${\displaystyle {\mathcal {M}}(H)}$. Let H_y (for y in Y) be sets of edges of H. For every subset Y₀ of Y, ${\displaystyle {\mathcal {M}}(H_{Y_{0}})}$ is the set of matchings in the sub-hypergraph:

${\displaystyle \bigcup _{y\in Y_{0}}H_{y}.}$

If, for every subset Y₀ of Y:

${\displaystyle \eta _{H}({\mathcal {M}}(H_{Y_{0}}))\geq |Y_{0}|}$

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

This is true, in particular, if we define H_y as the set of edges of H containing the vertex y of Y. In this case, ${\displaystyle {\mathcal {M}}(H_{Y_{0}})}$ is equivalent to N_H(Y₀) - the multi-hypergraph of neighbors of Y₀ ("multi" - since each neighbor is allowed to appear several times for several different y).

The matching complex of a hypergraph is exactly the independence complex of its line graph, denoted L(H). 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:

${\displaystyle \eta _{H}({\mathcal {M}}(H))\geq \Psi (L(H))}$

Combining the previous inequalities leads to the following condition.

Let H = (X + Y, E) be a bipartite hypergraph. Suppose that, for every subset Y₀ of Y, the following condition holds:

${\displaystyle \Psi (L(N_{H}(Y_{0})))\geq |Y_{0}|,}$

where N_H(Y₀) 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 Y₀). Then, H admits a Y-perfect matching.[14]

We consider several bipartite hypergraphs with Y = {1, 2} and X = {A, B; a, b, c}. The Meshulam condition trivially holds for the empty set. 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. It remains to check the subset Y itself. s

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

No necessary-and-sufficient condition using Ψ is known.

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

Let G = (X + Y, E) be a bipartite graph. Let X₀ be a subset of X and Y₀ a subset of Y. The condition "e ∩ X₀ ≥ |e ∩ Y₀| for all edges e in E" means that X₀ contains all the neighbors of vertices of Y_0- Hence, the CCKV condition becomes:

"If a subset X₀ of X contains the set N_H(Y₀), then |X₀| ≥ |Y₀|".

This is equivalent to Hall's condition.