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, ${\displaystyle \nu (H_{H}(Y_{0}))=|N_{H}(Y_{0})|=}$ 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, {i, x_i,1,1, ..., x_i,1,r−1}, ..., , {i, x_i,r-1,1, ..., x_i,r-1,r−1}.
  • E_m contains m-1 hyperedges of size r, {m, x_1,1,1, ..., x_1,r-1,r-1}, ..., , {m, x_m-1,1,1, ..., 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 ${\displaystyle H_{H}(Y_{0}\setminus \{m\})}$ contains at least ${\displaystyle (r-1)\cdot (|Y_{0}|-1)}$ hyperedges, and they are all disjoint.

The largest size of a fractional matching in H is denoted by ${\displaystyle \nu ^{*}(H)}$. Clearly ${\displaystyle \nu ^{*}(H)\geq \nu (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., ${\displaystyle \nu ^{*}(H)=|Y|}$. This is weaker than having a Y-perfect matching, which is equivalent to ${\displaystyle \nu (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, ${\displaystyle \tau (H_{H}(Y_{0}))=|N_{H}(Y_{0})|=}$ 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 (2 r - 3) cannot be improved. Let H = (X+Y, E) be an r-uniform bipartite hypergraph with:

• Y = {0,1}
• X = { x_ij : 1 ≤ i,j ≤ r-1 } [so |X| = (r-1)²].
• E = E₀ u E₁, where
  • E₀ = { {0, x_i1, ..., x_i(r-1) } | 1 ≤ i ≤ r-1 } [so E₀ contains r-1 hyperedges].
  • E₁ = { {1, x_1j[1], ..., x_{(r-1) j[r-1]} } | 1 ≤ j[k] ≤ r-1 for 1 ≤ k ≤ 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₀₀ u E₁₁) where:

• E₀₀ = { {x_i1, ..., x_i(r-1) } | 1 ≤ i ≤ r-1 } .
• E₁₁ = { {x_1j[1], ..., x_{(r-1) j[r-1]} } | 1 ≤ j[k] ≤ r-1 for 1 ≤ k ≤ r-1 }

One can visualize the vertices of X as arranged on an (r-1) times (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 ${\displaystyle r\geq 2}$ and ${\displaystyle \epsilon >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: w(N_H(Y₀))=mw(N_H(Y₀))=|N_H(Y₀)|. 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 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 = { {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_0. 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 U B - the union of all the H_i in B. Suppose that, for every sub-collection B of A, this U B contains a matching M(B) such that at least |B| disjoint subsets from U 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 |Y₀| disjoint edges from U {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 U B for every sub-collection B of A, such that, for pinning M(B), at least |B| edges from U {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}) u M({2}) u 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 different 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]

In a bipartite simple graph, the neighborhood-hypergraph contains just singletons - a singleton for every neighbor of Y₀ (some singletons appear more than once - if they are neighbors of different elements of Y₀). Its line-graph thus contains |N_H(Y₀)| vertex-disjoint cliques - a clique for every singleton. 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 becomes Hall's marriage condition.

We consider several bipartite graphs 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.

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 and 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.

• Rainbow-independent set

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 "${\displaystyle |e\cap X_{0}|\geq |e\cap Y_{0}|}$ for all edges e in E" means that X₀ contains all the neigbors 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.