Hall's marriage theorem
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: Let
be a finite family of sets (note that although
that can be obtained by choosing a distinct element from each set in
This concept can be formalized by defining a transversal to be the image of an injective function
An alternative term for transversal is system of distinct representatives.
If a transversal exists then the marriage condition must be true: the function
A lower bound on the different number of transversals that a given finite family
is an ordered sequence, so two different transversals could have exactly the same elements.
, because an alternating path to an unmatched vertex could be used to increase the size of the matching by toggling whether each of its edges belongs to
-perfect matching in this graph defines a system of unique representatives for
, such that any system of unique representatives for this family corresponds to an
Hall's theorem can be proved (non-constructively) based on Sperner's lemma.
More generally, any regular bipartite graph has a perfect matching.
[5] The marriage theorem is used in the usual proofs of the fact that an
By examining Philip Hall's original proof carefully, Marshall Hall Jr. (no relation to Philip Hall) was able to tweak the result in a way that permitted the proof to work for infinite
[10] This variant extends Philip Hall's Marriage theorem.
, is a (possibly infinite) family of finite sets that need not be distinct, then
The following example, due to Marshall Hall Jr., shows that the marriage condition will not guarantee the existence of a transversal in an infinite family in which infinite sets are allowed.
The marriage condition holds for this infinite family, but no transversal can be constructed.
Note that omitting in the graph yields the ordinary notion of comparing cardinalities.
The infinite marriage theorem states that there exists an injection from A to B in the graph, if and only if there is no subset C of A such that N(C) is strictly smaller than C in the graph.
[12] The more general problem of selecting a (not necessarily distinct) element from each of a collection of non-empty sets (without restriction as to the number of sets or the size of the sets) is permitted in general only if the axiom of choice is accepted.
A fractional matching in a graph is an assignment of non-negative weights to each edge, such that the sum of weights adjacent to each vertex is at most 1.
A fractional matching is X-perfect if the sum of weights adjacent to each vertex is exactly 1.
The following are equivalent for a bipartite graph G = (X+Y, E):[13] When Hall's condition does not hold, the original theorem tells us only that a perfect matching does not exist, but does not tell what is the largest matching that does exist.
To learn this information, we need the notion of deficiency of a graph.
The larger is the deficiency, the farther is the graph from satisfying Hall's condition.
Using Hall's marriage theorem, it can be proved that, if the deficiency of a bipartite graph G is d, then G admits a matching of size at least |X|-d.
This article incorporates material from proof of Hall's marriage theorem on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.
