Definitions and Statement of The Theorem
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 or "SDR".
The collection S satisfies the marriage condition (MC) 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 (SDR) if and only if S satisfies the marriage condition.
Read more about this topic: Hall's Marriage Theorem
Famous quotes containing the words definitions, statement and/or theorem:
“Lord Byron is an exceedingly interesting person, and as such is it not to be regretted that he is a slave to the vilest and most vulgar prejudices, and as mad as the winds?
There have been many definitions of beauty in art. What is it? Beauty is what the untrained eyes consider abominable.”
—Edmond De Goncourt (1822–1896)
“He that writes to himself writes to an eternal public. That statement only is fit to be made public, which you have come at in attempting to satisfy your own curiosity.”
—Ralph Waldo Emerson (1803–1882)
“To insure the adoration of a theorem for any length of time, faith is not enough, a police force is needed as well.”
—Albert Camus (1913–1960)