|
|
|
Revision difference : Hall's marriage theorem |
| Version current |
Version 2 |
| Let $S = \{ S_1,S_2,\dots S_n \}$ be a finite collection of finite sets. There exists a system of distinct representatives of $S$ if and only if the following condition holds for any $T \subseteq S$: |
Let $S = \{ S_1,S_2,\dots S_n \}$ be a finite collection of finite sets. There exists a system of distinct representatives of $S$ if and only if the following condition holds for any $T \subseteq S$: |
| $$\left | \cup T \right | \geq |T|$$ |
$$\left | \cup T \right | \geq |T|$$ |
|
|
| As a corollary, if this condition fails to hold anywhere, then no SDR exists. |
As a corollary, if this condition fails to hold anywhere, then no SDR exists. |
|
|
| This is known as Hall's marriage theorem. The name arises from a particular application of this theorem. Suppose we have a finite set of single men/women, and, for each man/woman, a finite collection of women/men to whom this person is attracted. An SDR for this collection would be a way each man/woman could be (theoretically) married happily. Hence, Hall's marriage theorem can be used to determine if this is possible. |
This is known as Hall's marriage theorem. The name arises from a particular application of this theorem. Suppose we have a finite set of single men/women, and, for each man/woman, a finite collection of women/men to whom this person is attracted. An SDR for this collection would be a way each man/woman could be (theoretically) married happily. Hence, Hall's marriage theorem can be used to determine if this is possible. |
|
|
| An application of this theorem to graph theory gives that if $G(V_1, V_2, E)$ is a bipartite graph, then $G$ has a complete matching that saturates every vertex of $V_1$ if and only if $|S|\leq |N(S)|$ for every subset $S\subset V_1$. |
|
|
|
|
|
