In mathematics, Hall's marriage theorem, proved by Philip Hall (1935), is a theorem with two equivalent formulations. In each case, the theorem gives a necessary and sufficient condition for an object to exist:
The combinatorial formulation answers whether a finite collection of sets has a transversal—that is, whether an element can be chosen from each set without repetition. Hall's condition is that for any subset of sets from the collection, the total unique elements they contain is at least as large as the number of sets in the subset. The graph theoretic formulation answers whether a finite bipartite graph has a perfect matching—that is, a way to match each vertex from one group uniquely to an adjacent vertex from the other group. Hall's condition is that any subset of vertices from one group has a neighbourhood of equal or greater size.
Combinatorial formulation
Statement Let F {\displaystyle {\mathcal {F}}} be a finite family of sets (note that although F {\displaystyle {\mathcal {F}}} is not itself allowed to be infinite, the sets in it may be so, and F {\displaystyle {\mathcal {F}}} may contain the same set multiple times). Let X {\displaystyle X} be the union of all the sets in F {\displaystyle {\mathcal {F}}} , the set of elements that belong to at least one of its sets. A transversal for F {\displaystyle {\mathcal {F}}} is a subset of X {\displaystyle X} that can be obtained by choosing a distinct element from each set in F {\displaystyle {\mathcal {F}}} . This concept can be formalized by defining a transversal to be the image of an injective function f : F → X {\displaystyle f:{\mathcal {F}}\to X} such that f ( S ) ∈ S {\displaystyle f(S)\in S} for each S ∈ F {\displaystyle S\in {\mathcal {F}}} . An alternative term for transversal is system of distinct representatives. The collection F {\displaystyle {\mathcal {F}}} satisfies the marriage condition when each subfamily of F {\displaystyle {\mathcal {F}}} contains at least as many distinct members as its number of sets. That is, for all G ⊆ F {\displaystyle {\mathcal {G}}\subseteq {\mathcal {F}}} ,
| G | ≤ | ⋃ S ∈ G S | . {\displaystyle |{\mathcal {G}}|\leq {\Bigl |}\bigcup _{S\in {\mathcal {G}}}S{\Bigr |}.}
If a transversal exists then the marriage condition must be true: the function f {\displaystyle f} used to define the transversal maps G {\displaystyle {\mathcal {G}}} to a subset of its union, of size equal to | G | {\displaystyle |{\mathcal {G}}|} , so the whole union must be at least as large. Hall's theorem states that the converse is also true:
The name "marriage theorem" came from (Halmos & Vaughan 1950)Suppose that each of a (possibly infinite) set of boys is acquainted with a finite set of girls. Under what conditions is it possible for each boy to marry one of his acquaintances? It is clearly necessary that every finite set of k boys be, collectively, acquainted with at least k girls... this condition is also sufficient.
Examples
… excerpt ends here. Continue reading the full article.
