Hall’s marriage theorem
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.
|Title||Hall’s marriage theorem|
|Date of creation||2013-03-22 12:35:14|
|Last modified on||2013-03-22 12:35:14|
|Last modified by||mathcam (2727)|