Hall-type theorems for hypergraphs

In combinatorics, Hall-type theorems for hypergraphs are several generalization of Hall's marriage theorem from graphs to hypergraphs. Such theorems were proved by Ofra Kessler[1][2], Ron Aharoni,[3][4], Penny Haxell,[5][6] Roy Meshulam,[7] 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 generalizaion 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.[1] 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 Y₀ of Y, the neighbors of Y₀ are the subsets of X that share hyperedges with vertices of Y₀. Formally: ${\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: 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₀. 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₀.

Since N_H(Y₀) 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₀). We call it the neighborhood-hypergraph of Y₀ and denote it by: ${\displaystyle H_{H}(Y_{0}):=(X,N_{H}(Y_{0}))}$. Note that, if H is a simple bipartite graph, the neighborhood-hypergraph of every Y₀ contains just the neighbors of Y₀ in X, each of which with a self-loop.

Insufficiency of Hall's condition

Hall's condition requires that, for each subset Y₀ of Y, the set of neighbors of Y₀ 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₀) contain at least |Y₀| disjoint edges, rather than just |Y₀| edges. In other words: H_H(Y₀) should contain a matching of size at least |Y₀|. The largest size of a matching in a hypergraph H is called its matching number and denoted by ${\displaystyle \nu (H)}$ (thus H admits a Y-perfect matching iff ${\displaystyle \nu (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, ${\displaystyle \nu (H_{H}(Y))=2}$ since H_H(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₀ of Y, the following inequality holds:

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

In words: the neighborhood-hypergraph of Y₀ admits a matching larger than (r - 1) (|Y₀| - 1). Then H admits a Y-perfect matching (as defined in 2. above).

This was first conjectured by Aharoni.[3] It was proved with Ofra Kessler for bipartite hypergraphs in which |Y| ≤ 4[1] and for |Y| = 5.[2] It was later proved for all r-uniform hypergraphs.[6]^{:Corollary 1.2}

In simple graphs

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.

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:

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

Fractional matchings

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|}$.

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 ${\displaystyle \tau (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₀ of Y, the following inequality holds:

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

In words: the neighborhood-hypergraph of Y₀ has no transversal of size (2 r - 3) (Y₀ - 1) or less.

Then, H admits a Y-perfect matching (as defined in 2. above).[5]^{:Theorem 3}

In simple graphs

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.

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:

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

Algorithms

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]

Aharoni–Haxell–Meshulam 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.[6] The width of a hypergraph H = (V, E) is the smallest size of a subset of E that pins E.[7] The matching width of a hypergraph H is the maximum, over all matchings M in H, 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. Suppose that, for every subset Y₀ of Y, the matching-width of N_H(Y₀) is at least |Y₀| [in other words: N_H(Y₀) contains a matching M(Y₀) such that at least |Y₀| disjoint edges from N_H(Y₀) are required for pinning M(Y₀)]. Then, H admits a Y-perfect matching.[6]^{:Theorem 1.1}

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₀ of Y, either the matching-width of N_H(Y₀) is at least |Y₀|, or the width of N_H(Y₀) is at least 2|Y₀|-1. Then, H admits a Y-perfect matching.[7]^{:Theorem 1.4}

In simple graphs

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). Thus, the Aharoni–Haxell condition becomes, for every subset Y₀ of Y:

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

This is exactly 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 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.

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

Necessary and sufficient condition

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.

Examples

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.

Proof

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.

Extensions

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

See also

• Rainbow-independent set

More conditions from rainbow matchings

A rainbow matching is a matching in a simple graph, in which each edge has a different "color". By treating the colors as vertices in the set Y, one can see that a rainbow matching is in fact a matching in a bipartite hypergraph. Thus, several sufficient conditions for the existence of a large rainbow matching can be translated to conditions for the existence of a large matching in a hypergraph.

The following results pertain to tripartite hypergraphs in which each of the 3 parts contains exactly n vertices, the degree of each vertex is exactly n, and the set of neighbors of every vertex is a matching (henceforth "n-tripartite-hypergraph"):

• Every n-tripartite-hypergraph has a matching of size 2n/3.[14]
• Every n-tripartite-hypergraph has a matching of size n - sqrt(n).[15]
• Every n-tripartite-hypergraph has a matching of size n - 11 log₂²(n).[16]
• H. J. Ryser conjectured that, when n is odd, every n-tripartite-hypergraph has a matching of size n.[17]
• S. K. Stein and Brualdi conjectured that, when n is even, every n-tripartite-hypergraph has a matching of size n-1.[18] (it is known that a matching of size n might not exist in this case).
• A more general conjecture of Stein is that a matching of size n-1 exists even without requiring that the set of neighbors of every vertex in Y is a matching.[17]

The following results pertain to more general bipartite hypergraphs:

• Any tripartite hypergraph (X₁+X₂+Y, E) in which |Y|=2n-1, the degree of each vertex y in Y is n, and the neighbor-set of y is a matching, has a matching of size n.[19] The 2n-1 is the best possible: if |Y|=2n-2, then the maximum matching may be of size n-1.
• Any bipartite hypergraph (X+Y, E) in which |Y|=3n-2, the degree of each vertex y in Y is n, and the neighbor-set of y is a matching, has a matching of size n.[19] It is not known whether this is the best possible. For even n, it is only known that 2n is required; for odd n, it is only known that 2n-1 is required.

Conforti-Cornuejols-Kapoor-Vuskovic condition: Balanced hypergraphs

A balanced hypergraph is an alternative generalization of a bipartite graph: it is a hypergraph in which every odd cycle C of H has an edge containing at least three vertices of C.

Let H = (V, E) be a balanced hypergraph. The following are equivalent:[20][21]

• H admits a perfect matching (i.e., a matching in which each vertex is matched).
• For all disjoint vertex-sets V₁, V₂, if |V₁| > |V₂|, then there exists an edge e in E such that ${\displaystyle |e\cap V_{1}|>|e\cap V_{2}|}$ (equivalently: if ${\displaystyle |e\cap V_{2}|\geq |e\cap V_{1}|}$ for all edges e in E, then |V₂| ≥ |V₁|).

In simple graphs

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.

See also

• Perfect matching in high-degree hypergraphs - presents other sufficient conditions for the existence of perfect matchings, which are based only on the degree of vertices.

References

1. Aharoni, Ron; Kessler, Ofra (1990-10-15). "On a possible extension of Hall's theorem to bipartite hypergraphs". Discrete Mathematics. 84 (3): 309–313. doi:10.1016/0012-365X(90)90136-6. ISSN 0012-365X.
2. Kessler, Ofra (1989). Matchings in Hypergraphs (D.Sc. Thesis). Haifa, Israel: Technion, Israel's institute of technology.
3. Aharoni, Ron (1985-12-01). "Matchings inn-partiten-graphs". Graphs and Combinatorics. 1 (1): 303–304. doi:10.1007/BF02582958. ISSN 1435-5914.
4. Aharoni, Ron (1993-06-01). "On a criterion for matchability in hypergraphs". Graphs and Combinatorics. 9 (2): 209–212. doi:10.1007/BF02988309. ISSN 1435-5914.
5. Haxell, P.E. (1995-09-01). "A condition for matchability in hypergraphs". Graphs and Combinatorics. doi:10.1007/bf01793010.
6. Aharoni, Ron; Haxell, Penny (2000). "Hall's theorem for hypergraphs". Journal of Graph Theory. 35 (2): 83–88. doi:10.1002/1097-0118(200010)35:23.0.CO;2-V. ISSN 1097-0118.
7. Meshulam, Roy (2001-01-01). "The Clique Complex and Hypergraph Matching". Combinatorica. 21 (1): 89–94. doi:10.1007/s004930170006. ISSN 1439-6912.
8. Annamalai, Chidambaram (2015-12-21), "Finding Perfect Matchings in Bipartite Hypergraphs", Proceedings of the 2016 Annual ACM-SIAM Symposium on Discrete Algorithms, Proceedings, Society for Industrial and Applied Mathematics, pp. 1814–1823, doi:10.1137/1.9781611974331.ch126, retrieved 2020-06-19
9. Asadpour Arash; Feige Uriel; Saberi Amin (2012-07-24). "Santa claus meets hypergraph matchings". ACM Transactions on Algorithms (TALG). doi:10.1145/2229163.2229168.
10. Annamalai Chidambaram; Kalaitzis Christos; Svensson Ola (2017-05-26). "Combinatorial Algorithm for Restricted Max-Min Fair Allocation". ACM Transactions on Algorithms (TALG). doi:10.1145/3070694.
11. Davies, Sami; Rothvoss, Thomas; Zhang, Yihao (2019-12-23), "A Tale of Santa Claus, Hypergraphs and Matroids", Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, Proceedings, Society for Industrial and Applied Mathematics, pp. 2748–2757, doi:10.1137/1.9781611975994.167, retrieved 2020-06-28
12. Aharoni, Ron (2001-01-01). "Ryser's Conjecture for Tripartite 3-Graphs". Combinatorica. 21 (1): 1–4. doi:10.1007/s004930170001. ISSN 1439-6912.
13. Kalai, Gil (2012-11-25). "Happy Birthday Ron Aharoni!". Combinatorics and more. Retrieved 2020-06-30.
14. Koksma, Klaas K. (1969-07-01). "A lower bound for the order of a partial transversal in a latin square". Journal of Combinatorial Theory. 7 (1): 94–95. doi:10.1016/s0021-9800(69)80009-8. ISSN 0021-9800.
15. Woolbright, David E (1978-03-01). "An n × n Latin square has a transversal with at least n−n distinct symbols". Journal of Combinatorial Theory, Series A. 24 (2): 235–237. doi:10.1016/0097-3165(78)90009-2. ISSN 0097-3165.
16. Hatami, Pooya; Shor, Peter W. (2008-10-01). "A lower bound for the length of a partial transversal in a Latin square". Journal of Combinatorial Theory, Series A. 115 (7): 1103–1113. doi:10.1016/j.jcta.2008.01.002. ISSN 0097-3165.
17. Aharoni, Ron; Berger, Eli; Kotlar, Dani; Ziv, Ran (2017-01-04). "On a conjecture of Stein". Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. 87 (2): 203–211. doi:10.1007/s12188-016-0160-3. ISSN 0025-5858.
18. Stein, Sherman (1975-08-01). "Transversals of Latin squares and their generalizations". Pacific Journal of Mathematics. 59 (2): 567–575. doi:10.2140/pjm.1975.59.567. ISSN 0030-8730.
19. Aharoni, Ron; Berger, Eli (2009-09-25). "Rainbow Matchings in $r$-Partite $r$-Graphs". The Electronic Journal of Combinatorics. 16 (1). doi:10.37236/208. ISSN 1077-8926.
20. Conforti, Michele; Cornuéjols, Gérard; Kapoor, Ajai; Vušković, Kristina (1996-09-01). "Perfect matchings in balanced hypergraphs". Combinatorica. 16 (3): 325–329. doi:10.1007/BF01261318. ISSN 1439-6912.
21. Huck, Andreas; Triesch, Eberhard (2002-07-01). "Perfect Matchings in Balanced Hypergraphs – A Combinatorial Approach". Combinatorica. 22 (3): 409–416. doi:10.1007/s004930200020. ISSN 1439-6912.