Hall's marriage theorem
Hall's marriage theorem, or simply Hall's theorem, proved by Philip Hall (1935), is a theorem with two equivalent formulations:
Let S be a family of finite sets, where the family may contain an infinite number of sets and the individual sets may be repeated multiple times.
A transversal for S is a set T and a bijection f from T to S such that for all t in T, t is a member of f(t). An alternative term for transversal is system of distinct representatives.
The collection S satisfies the marriage condition if and only if for each subcollection , we have
In other words, the number of sets in each subcollection W is less than or equal to the number of distinct elements in the union over the subcollection W.
Hall's theorem states that S has a transversal if and only if S satisfies the marriage condition.
Example 1: Consider S = {A1, A2, A3} with
A valid transversal would be (1, 4, 5). (Note this is not unique: (2, 1, 3) works equally well, for example.)
Example 2: Consider S = {A1, A2, A3, A4} with
No valid transversal exists; the marriage condition is violated as is shown by the subcollection {A2, A3, A4}.
Example 3: Consider S= {A1, A2, A3, A4} with
The only valid transversals are (c, b, a, d) and (c, d, a, b).
The standard example of an application of the marriage theorem is to imagine two groups; one of n men, and one of n women. For each woman, there is a subset of the men, any one of which she would happily marry; and any man would be happy to marry a woman who wants to marry him. Consider whether it is possible to pair up (in marriage) the men and women so that every person is happy.
...
Wikipedia