Hall's Marriage Theorem
Theorem
Finite Indexed Family of Finite Sets
Let $\SS = \family {S_k}_{k \mathop \in I}$ be a finite indexed family of finite sets.
For each $F \subseteq I$, let $\ds Y_F = \bigcup_{k \mathop \in F} S_k$.
Let $Y = Y_I$.
Then the following are equivalent:
- $(1): \quad \SS$ satisfies the marriage condition: for each finite subset $F \subseteq I : \card F \le \card {Y_F}$.
- $(2): \quad$ There exists an injection $f: I \to Y$ such that $\forall k \in I: \map f k \in S_k$.
General Indexed Family of Finite Sets
Let $\SS = \family {S_k}_{k \mathop \in I}$ be an indexed family of finite sets.
For each $F \subseteq I$, let $\ds Y_F = \bigcup_{k \mathop \in F} S_k$.
Let $Y = Y_I$.
Then the following are equivalent:
- $(1): \quad \SS$ satisfies the marriage condition: for each finite subset $F \subseteq I : \card F \le \card {Y_F}$.
- $(2): \quad$ There exists an injection $f: I \to Y$ such that $\forall k \in I: \map f k \in S_k$.
Explanation
This Hall's Marriage Theorem is so called for the following reason:
Let $I$ be a set of women.
Suppose that each woman $k$ is romantically interested in a finite set $S_k$ of men.
Suppose also that:
- each woman would like to marry exactly one of these men
and:
- each man in $\ds \bigcup_{k \mathop \in I} S_k$ would like to marry at most one woman in $I$.
Then this theorem gives a condition under which it is possible to match every woman to a man.
This article is complete as far as it goes, but it could do with expansion. In particular: Graph-theoretical formulation You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding this information. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Expand}} from the code.If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page. |
Source of Name
This entry was named for Philip Hall.