Hall-type theorems for hypergraphs

Hall's marriage theorem provides a condition guaranteeing that a bipartite graph {{math|(X + Y, E)}} admits a perfect matching, or - more generally - a matching that saturates all vertices of {{mvar|Y}}. The condition involves the number of neighbors of subsets of {{mvar|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, {{mvar|V}} can be partitioned into two sets {{mvar|X}} and {{mvar|Y}}, such that each hyperedge contains exactly one vertex of {{mvar|Y}}. A bipartite graph is a special case in which each edge contains exactly one vertex of {{mvar|Y}} and also exactly one vertex of {{mvar|X}}; in a bipartite hypergraph, each hyperedge contains exactly one vertex of {{mvar|Y}} but may contain zero or more vertices of {{mvar|X}}. For example, the hypergraph {{math|(V, E)}} with {{math|1=V = {1,2,3,4,5,6} }} and {{math|1=E = { {1,2,3}, {1,2,4}, {1,3,4}, {5,2}, {5,3,4,6} } }} is bipartite with {{math|1=Y = {1,5} }} and {{math|1=X = {2,3,4,6}.}}

2. Perfect matching: A matching in a hypergraph {{math|1=H = (V, E)}} is a subset {{mvar|F}} of {{mvar|E}}, such that every two hyperedges of {{mvar|F}} are disjoint. If {{mvar|H}} is bipartite with parts {{mvar|X}} and {{mvar|Y}}, then the size of each matching is obviously at most {{math|{{abs|Y}}}}. A matching is called {{mvar|Y}}-perfect (or {{mvar|Y}}-saturating) if its size is exactly {{math|{{abs|Y}}}}. In other words: every vertex of {{mvar|Y}} appears in exactly one hyperedge of {{mvar|M}}. This definition reduces to the standard definition of a {{mvar|Y}}-perfect matching in a bipartite graph.

3. Neighbors: Given a bipartite hypergraph {{math|1=H = (X + Y, E)}} and a subset {{math|Y{{sub|0}}}} of {{mvar|Y}}, the neighbors of {{math|Y{{sub|0}}}} are the subsets of {{mvar|X}} that share hyperedges with vertices of {{math|Y{{sub|0}}}}. Formally:

:$N\_H(Y\_0)\; :=\; \backslash \{X\_0\backslash subseteq\; X\; ~~|~~\; \backslash exists\; y\_0\backslash in\; Y\_0:\; ~\backslash \{y\_0\backslash \}\backslash cup\; X\_0\; \backslash in\; E\; \backslash \}.$

For example, in the hypergraph from point 1, we have: {{math|1=N{{sub|H}}({1}) = { {2,3}, {2,4}, {3,4} } }} and {{math|1=N{{sub|H}}({5}) = { {2}, {3,4,6} } }} and {{math|1=N{{sub|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 {{mvar|X}} that are adjacent to one or more vertices of {{math|Y{{sub|0}}}}. In a bipartite hypergraph, each neighbor is a set - the neighbors are the subsets of {{mvar|X}} that are "adjacent" to one or more vertices of {{math|Y{{sub|0}}}}.

Since {{math|N{{sub|H}}(Y{{sub|0}})}} contains only subsets of {{mvar|X}}, one can define a hypergraph in which the vertex set is {{mvar|X}} and the edge set is {{math|N{{sub|H}}(Y{{sub|0}})}}. We call it the neighborhood-hypergraph of {{math|Y{{sub|0}}}} and denote it:

:$H\_H(Y\_0)\; :=\; (X,\; N\_H(Y\_0)).$

Note that, if {{mvar|H}} is a simple bipartite graph, the neighborhood-hypergraph of every {{math|Y{{sub|0}}}} contains just the neighbors of {{math|Y{{sub|0}}}} in {{mvar|X}}, each of which with a self-loop.

Hall's condition requires that, for each subset {{math|Y{{sub|0}}}} of {{mvar|Y}}, the set of neighbors of {{math|Y{{sub|0}}}} is sufficiently large. With hypergraphs this condition is insufficient. For example, consider the tripartite hypergraph with edges:

{ {1, a, A}, {2, a, B} }

One could try to fix it by requiring that {{math|N{{sub|H}}(Y{{sub|0}})}} contain at least {{math|{{abs|Y{{sub|0}}}}}} disjoint edges, rather than just {{math|{{abs|Y{{sub|0}}}}}} edges. In other words: {{math|H{{sub|H}}(Y{{sub|0}})}} should contain a matching of size at least {{math|{{abs|Y{{sub|0}}}}}}. The largest size of a matching in a hypergraph {{mvar|H}} is called its matching number and denoted by {{math|ν(H)}} (thus {{mvar|H}} admits a {{mvar|Y}}-perfect matching if and only if {{math|1=ν(H) = {{abs|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} }

Thus, to guarantee a perfect matching, a stronger condition is needed. Various such conditions have been suggested.

Let {{math|1=H = (X + Y, E)}} be a bipartite hypergraph (as defined in 1. above), in which the size of every hyperedge is exactly {{mvar|r}}, for some integer {{math|r > 1}}. Suppose that, for every subset {{math|Y{{sub|0}}}} of {{mvar|Y}}, the following inequality holds:

:$\backslash nu(N\_H(Y\_0))\; \backslash geq\; (r-1)\backslash cdot\; (|Y\_0|\; -\; 1)\; +\; 1$

In words: the neighborhood-hypergraph of {{math|Y{{sub|0}}}} admits a matching larger than {{math|(r – 1) ({{abs|Y{{sub|0}}}} – 1)}}. Then {{mvar|H}} admits a {{mvar|Y}}-perfect matching (as defined in 2. above).

This was first conjectured by Aharoni. It was proved with Ofra Kessler for bipartite hypergraphs in which {{math|{{abs|Y}} ≤ 4}} and for {{math|1={{abs|Y}} = 5}}. It was later proved for all {{mvar|r}}-uniform hypergraphs.{{Rp|Corollary 1.2}}

For a bipartite simple graph {{math|1=r = 2}}, and Aharoni's condition becomes:

:$\backslash nu(H\_H(Y\_0))\; \backslash geq\; |Y\_0|.$

Moreover, the neighborhood-hypergraph (as defined in 3. above) contains just singletons - a singleton for every neighbor of {{math|Y{{sub|0}}}}. Since singletons do not intersect, the entire set of singletons is a matching. Hence, {{math|1=ν(H{{sub|H}}(Y{{sub|0}})) = {{abs|N{{sub|H}}(Y{{sub|0}})}} = }} the number of neighbors of {{math|Y{{sub|0}}}}. Thus, Aharoni's condition becomes, for every subset {{math|Y{{sub|0}}}} of {{mvar|Y}}:

:$|N\_H(Y\_0)|\; \backslash geq\; |Y\_0|.$

This is exactly Hall's marriage condition.

The following example shows that the factor {{math|(r – 1)}} cannot be improved. Choose some integer {{math|m > 1}}. Let {{math|1=H = (X + Y, E)}} be the following {{mvar|r}}-uniform bipartite hypergraph:

• {{math|1=Y = {1, ..., m};}}
• {{mvar|E}} is the union of {{math|E{{sub|1}}, … , E{{sub|m}}}} (where {{mvar|E{{sub|i}}}} is the set of hyperedges containing vertex {{mvar|i}}), and:
• For each {{mvar|i}} in {{math|{1, … , m – 1},}} {{mvar|E{{sub|i}}}} contains {{math|r – 1}} disjoint hyperedges of size {{mvar|r}}: $\backslash \{\; i,\; x\_\{i,1,1\},\; \backslash ldots,\; x\_\{i,1,r-1\}\; \backslash \},\; \backslash ldots\; ,\; \backslash \{i,\; x\_\{i,r-1,1\},\; \backslash ldots,\; x\_\{i,r-1,r-1\}\; \backslash \}.$
• {{mvar|E{{sub|m}}}} contains {{math|m – 1}} hyperedges of size {{mvar|r}}: $\backslash \{\; m,\; x\_\{1,1,1\},\; \backslash ldots,\; x\_\{1,r-1,r-1\},\; \backslash \}\; ,\; \backslash ldots,\; \backslash \{\; m,\; x\_\{m-1,1,1\},\; \backslash ldots,\; x\_\{m-1,r-1,1\}\; \backslash \}$

Note that edge {{mvar|i}} in {{mvar|E{{sub|m}}}} meets all edges in {{mvar|E{{sub|i}}}}.

This {{mvar|H}} does not admit a {{mvar|Y}}-perfect matching, since every hyperedge that contains {{mvar|m}} intersects all hyperedges in {{mvar|E{{sub|i}}}} for some {{math|i < m}}.

However, every subset {{math|Y{{sub|0}}}} of {{mvar|Y}} satisfies the following inequality

:$\backslash nu(H\_H(Y\_0))\; \backslash geq\; (r-1)\backslash cdot\; (|Y\_0|\; -\; 1)$

since {{math|H{{sub|H}}(Y{{sub|0}} \ {m})}} contains at least {{math|(r – 1) ⋅ ({{abs|Y{{sub|0}}}} – 1)}} hyperedges, and they are all disjoint.

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

:$\backslash nu^*(H\_H(Y\_0))\; \backslash geq\; (r-1)\backslash cdot\; (|Y\_0|\; -\; 1)\; +1$

It was conjectured that in this case, too, {{mvar|H}} admits a {{mvar|Y}}-perfect matching. This stronger conjecture was proved for bipartite hypergraphs in which {{math|1={{abs|Y}} = 2}}.

Later it was proved that, if the above condition holds, then {{mvar|H}} admits a {{mvar|Y}}-perfect fractional matching, i.e., {{math|1=ν*(H) = {{abs|Y}}}}. This is weaker than having a {{mvar|Y}}-perfect matching, which is equivalent to {{math|1=ν(H) = {{abs|Y}}}}.

A transversal (also called vertex-cover or hitting-set) in a hypergraph {{math|1={{mvar|H}} = (V, E)}} is a subset {{mvar|U}} of {{mvar|V}} such that every hyperedge in {{mvar|E}} contains at least one vertex of {{mvar|U}}. The smallest size of a transversal in {{mvar|H}} is denoted by {{math|τ(H)}}.

Let {{math|1=H = (X + Y, E)}} be a bipartite hypergraph in which the size of every hyperedge is at most {{mvar|r}}, for some integer {{math|r > 1}}. Suppose that, for every subset {{math|Y{{sub|0}}}} of {{mvar|Y}}, the following inequality holds:

:$\backslash tau(H\_H(Y\_0))\; \backslash geq\; (2r-3)\backslash cdot\; (|Y\_0|\; -\; 1)\; +\; 1$

In words: the neighborhood-hypergraph of {{math|Y{{sub|0}}}} has no transversal of size {{math|(2r – 3)(Y{{sub|0}} – 1)}} or less.

Then, {{mvar|H}} admits a {{mvar|Y}}-perfect matching (as defined in 2. above).{{Rp|Theorem 3}}

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

:$\backslash tau(H\_H(Y\_0))\; \backslash geq\; |Y\_0|.$

Moreover, the neighborhood-hypergraph (as defined in 3. above) contains just singletons - a singleton for every neighbor of {{math|Y{{sub|0}}}}. In a hypergraph of singletons, a transversal must contain all vertices. Hence, {{math|1=τ(H{{sub|H}}(Y{{sub|0}})) = {{abs|N{{sub|H}}(Y{{sub|0}})}} = }} the number of neighbors of {{math|Y{{sub|0}}}}. Thus, Haxell's condition becomes, for every subset {{math|Y{{sub|0}}}} of {{mvar|Y}}:

:$|N\_H(Y\_0)|\; \backslash 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 {{math|(2r – 3)}} cannot be improved. Let {{math|1=H = (X + Y, E)}} be an {{mvar|r}}-uniform bipartite hypergraph with:

• $Y\; =\; \backslash \{\; 0,1\; \backslash \}$
• $X\; =\; \backslash \{\; x\_\{ij\}\; :\; 1\; \backslash leq\; i,j\; \backslash leq\; r-1\; \backslash \}$ [so {{math|1={{abs|X}} = (r – 1){{sup|2}}}}].

• $E\; =\; E\_0\; \backslash cup\; E\_1,$ where:
• $E\_0\; =\; \backslash \{\; \backslash \{\; 0,\; x\_\{i1\},\; \backslash ldots,\; x\_\{i(r-1)\}\; \backslash \}\; |\; 1\; \backslash leq\; i\; \backslash leq\; r-1\; \backslash \}$
  [so {{math|E{{sub|0}}}} contains {{math|r – 1}} hyperedges].
• $E\_1\; =\; \backslash \{\; \backslash \{\; 1,\; x\_\{1j[1]\},\; \backslash ldots,\; x\_\{(r-1)\; j[r-1]\}\; \backslash \}\; |\; 1\; \backslash leq\; j[k]\; \backslash leq\; r-1$
  for $1\; \backslash leq\; k\; \backslash leq\; r-1\; \backslash \}$
  [so {{math|E{{sub|1}}}} contains {{math|(r – 1){{sup|r-1}}}} hyperedges].

This {{mvar|H}} does not admit a {{mvar|Y}}-perfect matching, since every hyperedge that contains 0 intersects every hyperedge that contains 1.

However, every subset {{math|Y{{sub|0}}}} of {{mvar|Y}} satisfies the following inequality:

:$\backslash tau(H\_H(Y\_0))\; \backslash geq\; (2r-3)\backslash 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 {{math|1=Y{{sub|0}} = Y}}, since it is the only subset for which the right-hand side is larger than 0. The neighborhood-hypergraph of {{mvar|Y}} is {{math|(X, E{{sub|00}} ∪ E{{sub|11}})}} where:

:$E\_\{00\}\; =\; \backslash \{\; \backslash \{\; x\_\{i1\},\; \backslash ldots,\; x\_\{i(r-1)\}\; \backslash \}\; |\; 1\; \backslash leq\; i\; \backslash leq\; r-1\; \backslash \}$

:$E\_\{11\}\; =\; \backslash \{\; \backslash \{\; x\_\{1j[1]\},\; \backslash ldots,\; x\_\{(r-1)\; j[r-1]\}\; \backslash \}\; |\; 1\; \backslash leq\; j[k]\; \backslash leq\; r-1$

::for $1\; \backslash leq\; k\; \backslash leq\; r-1\; \backslash \}$

One can visualize the vertices of {{mvar|X}} as arranged on an {{math|(r – 1) × (r – 1)}} grid. The hyperedges of {{math|E{{sub|00}}}} are the {{math|r – 1}} rows. The hyperedges of {{math|E{{sub|11}}}} are the {{math|(r – 1){{sup|r-1}}}} selections of a single element in each row and each column. To cover the hyperedges of {{math|E{{sub|10}}}} we need {{math|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., {{math|v{{sub|i1}}}} for each {{mvar|i}} in {{math|{1, …, r – 1})}}. Now, since {{math|E{{sub|11}}}} contains all columns, we need at least {{math|r – 2}} additional vertices - one vertex for each column {{math|{2, …, r}.}} All in all, each transversal requires at least {{math|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.{{Citation|last=Annamalai|first=Chidambaram|title=Finding Perfect Matchings in Bipartite Hypergraphs|date=2015-12-21|work=Proceedings of the 2016 Annual ACM-SIAM Symposium on Discrete Algorithms|pages=1814–1823|series=Proceedings|publisher=Society for Industrial and Applied Mathematics|doi=10.1137/1.9781611974331.ch126|isbn=978-1-61197-433-1|doi-access=free|arxiv=1509.07007}}

For every fixed choice of {{math|r ≥ 2}} and {{math|ε > 0}}, there exists an algorithm that finds a {{mvar|Y}}-perfect matching in every {{mvar|r}}-uniform bipartite hypergraph satisfying, for every subset {{math|Y{{sub|0}}}} of {{mvar|Y}}:

:$\backslash tau(H\_H(Y\_0))\; \backslash geq\; (2r-3\; +\backslash epsilon)\backslash cdot\; (|Y\_0|\; -\; 1)\; +\; 1$

In fact, in any {{mvar|r}}-uniform hypergraph, the algorithm finds either a {{mvar|Y}}-perfect matching, or a subset {{math|Y{{sub|0}}}} violating the above inequality.

The algorithm runs in time polynomial in the size of {{mvar|H}}, but exponential in {{mvar|r}} and {{math|{{frac|1|ε}}}}.

It is an open question whether there exists an algorithm with run-time polynomial in either {{mvar|r}} or {{math|{{frac|1|ε}}}} (or both).

Similar algorithms have been applied for solving problems of fair item allocation, in particular the santa-claus problem.{{Cite journal|last1=Asadpour Arash|last2=Feige Uriel|last3=Saberi Amin|date=2012-07-24|title=Santa claus meets hypergraph matchings|journal=ACM Transactions on Algorithms |language=EN|volume=8|issue=3|pages=1–9|doi=10.1145/2229163.2229168|s2cid=10281304}}{{Cite journal|last1=Annamalai Chidambaram|last2=Kalaitzis Christos|last3=Svensson Ola|date=2017-05-26|title=Combinatorial Algorithm for Restricted Max-Min Fair Allocation|journal=ACM Transactions on Algorithms |language=EN|volume=13|issue=3|pages=1–28|doi=10.1145/3070694|arxiv=1409.0607|s2cid=14749011}}{{Citation|last1=Davies|first1=Sami|title=A Tale of Santa Claus, Hypergraphs and Matroids|date=2019-12-23|work=Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms|pages=2748–2757|series=Proceedings|publisher=Society for Industrial and Applied Mathematics|doi=10.1137/1.9781611975994.167|last2=Rothvoss|first2=Thomas|last3=Zhang|first3=Yihao|isbn=978-1-61197-599-4|s2cid=49880727|doi-access=free|arxiv=1807.07189}}

We say that a set {{mvar|K}} of edges pins another set {{mvar|F}} of edges if every edge in {{mvar|F}} intersects some edge in {{mvar|K}}. The width of a hypergraph {{math|1=H = (V, E)}}, denoted {{math|w(H)}}, is the smallest size of a subset of {{mvar|E}} that pins {{mvar|E}}.{{Cite journal|last=Meshulam|first=Roy|date=2001-01-01|title=The Clique Complex and Hypergraph Matching|journal=Combinatorica|language=en|volume=21|issue=1|pages=89–94|doi=10.1007/s004930170006|s2cid=207006642|issn=1439-6912}} The matching width of a hypergraph {{mvar|H}}, denoted {{math|mw(H)}}, is the maximum, over all matchings {{mvar|M}} in {{mvar|H}}, of the minimum size of a subset of {{mvar|E}} that pins {{mvar|M}}. Since {{mvar|E}} contains all matchings in {{mvar|E}}, the width of H is obviously at least as large as the matching-width of {{mvar|H}}.

Aharoni and Haxell proved the following condition:

Let {{math|1=H = (X + Y, E)}} be a bipartite hypergraph. Suppose that, for every subset {{math|Y{{sub|0}}}} of {{mvar|Y}}, the following inequality holds:

$mw(N\_H(Y\_0))\; \backslash geq\; |Y\_0|$

[in other words: {{math|N{{sub|H}}(Y{{sub|0}})}} contains a matching {{math|M(Y{{sub|0}})}} such that at least {{math|{{abs|Y{{sub|0}}}}}} disjoint edges from {{math|N{{sub|H}}(Y{{sub|0}})}} are required for pinning {{math|M(Y{{sub|0}})}}]. Then, {{mvar|H}} admits a {{mvar|Y}}-perfect matching.{{Rp|Theorem 1.1}}

Let {{math|1=H = (X + Y, E)}} be a bipartite hypergraph. Suppose that, for every subset {{math|Y{{sub|0}}}} of {{mvar|Y}}, at least one of the following conditions hold:

$mw(N\_H(Y\_0))\; \backslash geq\; |Y\_0|$ or

$w(N\_H(Y\_0))\; \backslash geq\; 2\; |Y\_0|\; -\; 1$

Then, {{mvar|H}} admits a {{mvar|Y}}-perfect matching.{{Rp|Theorem 1.4}}

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

:$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 {{math|1=Y = {1, 2} }} and {{math|1=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 {{mvar|Y}} is contained in at least one edge, which is easy to check. It remains to check the subset {{mvar|Y}} itself.

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

Consider a bipartite hypergraph {{math|1=H = (X + Y, E)}} where {{math|1=Y = {1, …, m}.}} The Hall-type theorems do not care about the set {{mvar|Y}} itself - they only care about the neighbors of elements of {{mvar|Y}}. Therefore {{mvar|H}} can be represented as a collection of families of sets {{math|{H{{sub|1}}, …, H{{sub|m}}},}} where for each {{mvar|i}} in {{math|[m]}}, {{math|1=H{{sub|i}} := N{{sub|H}}({i}) =}} the set-family of neighbors of {{mvar|i}}. For every subset {{math|Y{{sub|0}}}} of {{mvar|Y}}, the set-family {{math|N{{sub|H}}(Y{{sub|0}})}} is the union of the set-families {{mvar|H{{sub|i}}}} for {{mvar|i}} in {{math|Y{{sub|0}}}}. A perfect matching in {{mvar|H}} is a set-family of size {{mvar|m}}, where for each {{mvar|i}} in {{math|[m]}}, the set-family {{mvar|H{{sub|i}}}} is represented by a set {{mvar|R{{sub|i}}}} in {{mvar|H{{sub|i}}}}, and the representative sets {{mvar|R{{sub|i}}}} are pairwise-disjoint.

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

Let {{math|1=A = {H{{sub|1}}, …, H{{sub|m}}} }} be a collection of families of sets. For every sub-collection {{mvar|B}} of {{mvar|A}}, consider the set-family {{math|∪ B}} - the union of all the {{mvar|H{{sub|i}}}} in {{mvar|B}}. Suppose that, for every sub-collection {{mvar|B}} of {{mvar|A}}, this {{math|∪ B}} contains a matching {{math|M(B)}} such that at least {{math|{{abs|B}}}} disjoint subsets from {{math|∪ B}} are required for pinning {{math|M(B)}}. Then {{mvar|A}} admits a system of disjoint representatives.

Let {{math|1=H = (X + Y, E)}} be a bipartite hypergraph. The following are equivalent:{{Rp|Theorem 4.1}}

• {{mvar|H}} admits a {{mvar|Y}}-perfect matching.
• There is an assignment of a matching {{math|M(Y{{sub|0}})}} in {{math|N{{sub|H}}(Y{{sub|0}})}} for every subset {{math|Y{{sub|0}}}} of {{mvar|Y}}, such that pinning {{math|M(Y{{sub|0}})}} requires at least {{math|{{abs|{{sub|0}}}}}} disjoint edges from {{math|∪ {M(Y{{sub|1}}): Y{{sub|1}}}} is a subset of {{math|Y{{sub|0}}}.}}

In set-family formulation: let {{math|1=A = {H{{sub|1}}, …, H{{sub|m}}} }} be a collection of families of sets. The following are equivalent:

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

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

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

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

But in the necessary condition, pinning {{math|M({1,2})}} required at least two edges from {{math|1=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.{{Cite web|last=Kalai|first=Gil|date=2012-11-25|title=Happy Birthday Ron Aharoni!|url=https://gilkalai.wordpress.com/2012/11/25/happy-birthday-ron-aharoni/|access-date=2020-06-30|website=Combinatorics and more|language=en}}

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

Let {{math|1=Y = {1, …, m}.}} They consider an {{mvar|m}}-vertex simplex, and prove that it admits a triangulation {{mvar|T}} with some special properties that they call economically-hierarchic triangulation. Then they label each vertex of {{mvar|T}} with a hyperedge from {{math|N{{sub|H}}(Y)}} in the following way:

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

Their sufficient condition implies that such a labeling exists. Then, they color each vertex {{mvar|v}} of {{mvar|T}} with a color {{mvar|i}} such that the hyperedge assigned to {{mvar|v}} is a neighbor of {{mvar|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 {{mvar|m}} hyperedges, each of which is a neighbor of a dif and only iferent element of {{mvar|Y}}, and so they must be disjoint. This is the desired {{mvar|Y}}-perfect matching.

The Aharoni–Haxell theorem has a deficiency version. It is used to prove Ryser's conjecture for {{math|1=r = 3}}.{{Cite journal|last=Aharoni|first=Ron|date=2001-01-01|title=Ryser's Conjecture for Tripartite 3-Graphs|journal=Combinatorica|language=en|volume=21|issue=1|pages=1–4|doi=10.1007/s004930170001|s2cid=13307018|issn=1439-6912}}

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

:$V\_\{Y\_0\}\; :=\; \backslash bigcup\_\{y\backslash in\; Y\_0\}\; V\_y.$

Suppose that, for every subset {{math|Y{{sub|0}}}} of {{mvar|Y}}, the homological connectivity plus 2 of the sub-complex induced by $V\_\{Y\_0\}$ is at least {{math|{{abs|Y{{sub|0}}}}}}, that is:

:$\backslash eta\_H(C[V\_\{Y\_0\}])\; \backslash geq\; |Y\_0|.$

Then there exists a {{mvar|C-V-}}transversal. That is: there is a set in {{mvar|C}} that intersects each {{mvar|V{{sub|y}}}} by exactly one element. This theorem has a deficiency version.{{cite arXiv|last1=Aharoni|first1=Ron|last2=Berger|first2=Eli|last3=Briggs|first3=Joseph|last4=Segal-Halevi|first4=Erel|last5=Zerbib|first5=Shira|date=2020-11-02|title=Fractionally balanced hypergraphs and rainbow KKM theorems|class=math.CO|eprint=2011.01053}} If, for every subset {{math|Y{{sub|0}}}} of {{mvar|Y}}:

:$\backslash eta\_H(C[V\_\{Y\_0\}])\; \backslash geq\; |Y\_0|-d,$

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

:$\backslash eta\_H(C[V\_\{Y\_0\}])\; \backslash geq\; g(|Y\_0|),$

then there is a set in {{mvar|C}} that intersects at least {{math|g({{abs|Y}})}} of the {{mvar|V{{sub|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 {{mvar|G}} (the score of CON when both players play optimally) is denoted by {{math|Ψ(G)}}. This number can be used to get a lower bound on the homological connectivity of the independence complex of {{mvar|G}}, denoted {{tmath|\mathcal{I}(G)}}:

:$\backslash eta\_H(\backslash mathcal\{I\}(G))\; \backslash geq\; \backslash Psi(G).$

Therefore, the above theorem implies the following. Let {{mvar|V}} be a set of vertices. Let {{mvar|G}} be a graph on {{mvar|V}}. Suppose that, for every subset {{math|Y{{sub|0}}}} of {{mvar|Y}}:

:$\backslash Psi(G[V\_\{Y\_0\}])\; \backslash geq\; |Y\_0|.$

Then there is an independent set in {{mvar|G}}, that intersects each {{mvar|V{{sub|y}}}} by exactly one element.

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

:$\backslash Psi(G[V\_\{Y\_0\}])\; \backslash geq\; |Y\_0|$

is equivalent to Hall's marriage condition. Here, the sets {{mvar|V{{sub|y}}}} are pairwise-disjoint, so a {{mvar|C}}-transversal contains a unique element from each {{mvar|V{{sub|y}}}}, which is equivalent to a {{mvar|Y}}-saturating matching.

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

:$\backslash bigcup\_\{y\backslash in\; Y\_0\}\; H\_y.$

If, for every subset {{math|Y{{sub|0}}}} of {{mvar|Y}}:

:$\backslash eta\_H(\backslash mathcal\{M\}(H\_\{Y\_0\}))\; \backslash geq\; |Y\_0|$

Then there exists a matching that intersects each set {{mvar|H{{sub|y}}}} exactly once (it is also called a rainbow matching, since each {{mvar|H{{sub|y}}}} can be treated as a color).

This is true, in particular, if we define {{mvar|H{{sub|y}}}} as the set of edges of {{mvar|H}} containing the vertex {{mvar|y}} of {{mvar|Y}}. In this case, {{tmath|\mathcal{M}(H_{Y_0})}} is equivalent to {{math|N{{sub|H}}(Y{{sub|0}})}} - the multi-hypergraph of neighbors of {{math|Y{{sub|0}}}} ("multi" - since each neighbor is allowed to appear several times for several different {{mvar|y}}).

The matching complex of a hypergraph is exactly the independence complex of its line graph, denoted {{math|L(H)}}. This is a graph in which the vertices are the edges of {{mvar|H}}, and two such vertices are connected iff their corresponding edges intersect in {{mvar|H}}. Therefore, the above theorem implies:

:$\backslash eta\_H(\backslash mathcal\{M\}(H))\; \backslash geq\; \backslash Psi(L(H))$

Combining the previous inequalities leads to the following condition.

:Let {{math|1=H = (X + Y, E)}} be a bipartite hypergraph. Suppose that, for every subset {{math|Y{{sub|0}}}} of {{mvar|Y}}, the following condition holds:

::$\backslash Psi(L(N\_H(Y\_0)))\; \backslash geq\; |Y\_0|,$

:where {{math|N{{sub|H}}(Y{{sub|0}})}} 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 {{math|Y{{sub|0}}}}). Then, {{mvar|H}} admits a {{mvar|Y}}-perfect matching.{{Cite journal|last=Meshulam|first=Roy|date=2003-05-01|title=Domination numbers and homology|journal=Journal of Combinatorial Theory | series=Series A|language=en|volume=102|issue=2|pages=321–330|doi=10.1016/S0097-3165(03)00045-1|issn=0097-3165|doi-access=free}}

We consider several bipartite hypergraphs with {{math|1=Y = {1, 2} }} and {{math|1=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 {{mvar|Y}} is non-empty (so it requires at least one explosion to destroy), which is easy to check. It remains to check the subset {{mvar|Y}} itself.

s

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

No necessary-and-sufficient condition using {{math|Ψ}} is known.

{{See also|Rainbow-independent set|Latin square#Transversals and 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 {{mvar|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 {{mvar|n}} vertices, the degree of each vertex is exactly {{mvar|n}}, and the set of neighbors of every vertex is a matching (henceforth "{{mvar|n}}-tripartite-hypergraph"):

• Every {{mvar|n}}-tripartite-hypergraph has a matching of size {{math|{{frac|2n|3}}}}.{{Cite journal|last=Koksma|first=Klaas K.|date=1969-07-01|title=A lower bound for the order of a partial transversal in a latin square|journal=Journal of Combinatorial Theory|volume=7|issue=1|pages=94–95|doi=10.1016/s0021-9800(69)80009-8|issn=0021-9800|doi-access=free}}
• Every {{mvar|n}}-tripartite-hypergraph has a matching of size {{math|n – {{radic|n}}}}.{{Cite journal|last=Woolbright|first=David E|date=1978-03-01|title=An n × n Latin square has a transversal with at least n−n distinct symbols|journal=Journal of Combinatorial Theory | series=Series A|volume=24|issue=2|pages=235–237|doi=10.1016/0097-3165(78)90009-2|issn=0097-3165|doi-access=free}}
• Every {{mvar|n}}-tripartite-hypergraph has a matching of size {{math|n – 11 log{{sub|2}}{{sup|2}}(n)}}.{{Cite journal|last1=Hatami|first1=Pooya|last2=Shor|first2=Peter W.|date=2008-10-01|title=A lower bound for the length of a partial transversal in a Latin square|journal=Journal of Combinatorial Theory | series=Series A |volume=115|issue=7|pages=1103–1113|doi=10.1016/j.jcta.2008.01.002|issn=0097-3165|doi-access=free}}
• Every {{mvar|n}}-tripartite-hypergraph has a matching of size {{math|n – O(log n/log log n)}}.{{Cite journal |last1=Keevash |first1=Peter |last2=Pokrovskiy |first2=Alexey |last3=Sudakov |first3=Benny |last4=Yepremyan |first4=Liana |date=2022-04-15 |title=New bounds for Ryser's conjecture and related problems |url=https://www.ams.org/btran/2022-09-08/S2330-0000-2022-00092-3/ |journal=Transactions of the American Mathematical Society, Series B |language=en |volume=9 |issue=8 |pages=288–321 |doi=10.1090/btran/92 |issn=2330-0000|doi-access=free |arxiv=2005.00526 }}
• Every {{mvar|n}}-tripartite-hypergraph has a matching of size {{math|n – 1}}.{{Cite arXiv |last=Montgomery |first=Richard |date=2023 |title=A proof of the Ryser-Brualdi-Stein conjecture for large even n |class=math.CO |eprint=2310.19779}} (Preprint)
• H. J. Ryser conjectured that, when {{mvar|n}} is odd, every {{mvar|n}}-tripartite-hypergraph has a matching of size {{mvar|n}}.{{Cite journal|last1=Aharoni|first1=Ron|last2=Berger|first2=Eli|last3=Kotlar|first3=Dani|last4=Ziv|first4=Ran|date=2017-01-04|title=On a conjecture of Stein|journal=Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg|volume=87|issue=2|pages=203–211|doi=10.1007/s12188-016-0160-3|s2cid=119139740|issn=0025-5858}}
• S. K. Stein and Brualdi conjectured that, when {{mvar|n}} is even, every {{mvar|n}}-tripartite-hypergraph has a matching of size {{math|n – 1}}.{{Cite journal|last=Stein|first=Sherman|date=1975-08-01|title=Transversals of Latin squares and their generalizations|journal=Pacific Journal of Mathematics|volume=59|issue=2|pages=567–575|doi=10.2140/pjm.1975.59.567|issn=0030-8730|doi-access=free}} (it is known that a matching of size {{mvar|n}} might not exist in this case).
• A more general conjecture of Stein is that a matching of size {{math|n – 1}} exists even without requiring that the set of neighbors of every vertex in {{mvar|Y}} is a matching.

The following results pertain to more general bipartite hypergraphs:

• Any tripartite hypergraph {{math|(X{{sub|1}} + X{{sub|2}} + Y, E)}} in which {{math|1={{abs|Y}} = 2n – 1}}, the degree of each vertex {{mvar|y}} in {{mvar|Y}} is {{mvar|n}}, and the neighbor-set of {{mvar|y}} is a matching, has a matching of size {{mvar|n}}.{{Cite journal|last1=Aharoni|first1=Ron|last2=Berger|first2=Eli|date=2009-09-25|title=Rainbow Matchings in $r$-Partite $r$-Graphs|journal=The Electronic Journal of Combinatorics|volume=16|issue=1|doi=10.37236/208|issn=1077-8926|doi-access=free}} The {{math|2n – 1}} is the best possible: if {{math|1={{abs|Y}} = 2n – 2}}, then the maximum matching may be of size {{mvar|n}}-1.
• Any bipartite hypergraph {{math|(X + Y, E)}} in which {{math|1={{abs|Y}} = 3n – 2}}, the degree of each vertex y in {{mvar|Y}} is {{mvar|n}}, and the neighbor-set of {{mvar|y}} is a matching, has a matching of size {{mvar|n}}. It is not known whether this is the best possible. For even {{mvar|n}}, it is only known that {{math|2n}} is required; for odd {{mvar|n}}, it is only known that {{math|2n – 1}} is required.

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

Let {{math|1=H = (V, E)}} be a balanced hypergraph. The following are equivalent:{{Cite journal|last1=Conforti|first1=Michele|last2=Cornuéjols|first2=Gérard|last3=Kapoor|first3=Ajai|last4=Vušković|first4=Kristina|author4-link= Kristina Vušković |date=1996-09-01|title=Perfect matchings in balanced hypergraphs|journal=Combinatorica|language=en|volume=16|issue=3|pages=325–329|doi=10.1007/BF01261318|s2cid=206792822|issn=1439-6912}}{{Cite journal|last1=Huck|first1=Andreas|last2=Triesch|first2=Eberhard|date=2002-07-01|title=Perfect Matchings in Balanced Hypergraphs – A Combinatorial Approach|journal=Combinatorica|language=en|volume=22|issue=3|pages=409–416|doi=10.1007/s004930200020|s2cid=34490040|issn=1439-6912}}

• {{mvar|H}} admits a perfect matching (i.e., a matching in which each vertex is matched).
• For all disjoint vertex-sets {{math|V{{sub|1}}}}, {{math|V{{sub|2}}}}, if {{math|{{abs|V{{sub|1}}}} > {{abs|V{{sub|2}}}}}}, then there exists an edge {{mvar|e}} in {{mvar|E}} such that {{math|{{abs|e ∩ V{{sub|1}}}} > {{abs|e ∩ V{{sub|2}}}}}} (equivalently: if {{math|{{abs|e ∩ V{{sub|2}}}} ≥ {{abs|e ∩ V{{sub|1}}}}}} for all edges {{mvar|e}} in {{mvar|E}}, then {{math|{{abs|V{{sub|2}}}} ≥ {{abs|V{{sub|1}}}}}}).

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

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

"If a subset {{math|X{{sub|0}}}} of {{mvar|X}} contains the set {{math|N{{sub|H}}(Y{{sub|0}})}}, then {{math|{{abs|X{{sub|0}}}} ≥ {{abs|Y{{sub|0}}}}}}".

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

Category:Hypergraphs

Category:Matching (graph theory)

Category:Theorems in graph theory

Category:Graph algorithms