|
|
| Line 1: |
Line 1: |
| In [[Combinatorics|combinatorial mathematics]], '''Hall's marriage theorem''', or simply '''Hall's theorem''', gives a necessary and sufficient condition for being able to select a distinct element from each of a collection of finite sets. It was proved by {{harvs|txt|first=Philip|last=Hall|authorlink=Philip Hall|year=1935}}.
| | Not much to say about myself I think.<br>Yes! Im a part of this site.<br>I really wish I am useful in one way .<br><br>my website [http://safedietsthatwork.buzznet.com/user/journal/ diet plans] |
| | |
| ==Definitions and statement of the theorem==
| |
| Let ''S'' be a [[Family of sets|family]] of [[finite set|finite]] sets, where the family may contain an infinite number of sets and the individual sets may be repeated multiple times.<ref>{{harvnb|Hall, Jr.|1986|loc=pg. 51}}. It is also possible to have infinite sets in the family, but the number of sets in the family must then be finite, counted with multiplicity. Only the situation of having an infinite number of sets while allowing infinite sets is not allowed.</ref>
| |
| | |
| A ''[[Transversal (combinatorics)|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 <math>W \subseteq S</math>, we have
| |
| | |
| :<math>|W| \le \Bigl|\bigcup_{A \in W} A\Bigr|.</math>
| |
| | |
| 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.
| |
| | |
| ==Discussion and examples==
| |
| Example 1: Consider ''S'' = {''A''<sub>''1''</sub>, ''A''<sub>''2''</sub>, ''A''<sub>''3''</sub>} with
| |
| :''A''<sub>''1''</sub> = {1, 2, 3}
| |
| :''A''<sub>''2''</sub> = {1, 4, 5}
| |
| :''A''<sub>''3''</sub> = {3, 5}.
| |
| | |
| A valid SDR would be (1, 4, 5). (Note this is not unique: (2, 1, 3) works equally well, for example.)
| |
| | |
| Example 2: Consider ''S'' = {''A''<sub>''1''</sub>, ''A''<sub>''2''</sub>, ''A''<sub>''3''</sub>, ''A''<sub>''4''</sub>} with
| |
| :''A''<sub>''1''</sub> = {2, 3, 4, 5}
| |
| :''A''<sub>''2''</sub> = {4, 5}
| |
| :''A''<sub>''3''</sub> = {5}
| |
| :''A''<sub>''4''</sub> = {4}.
| |
| | |
| No valid SDR exists; the marriage condition is violated as is shown by the subcollection {''A''<sub>''2''</sub>, ''A''<sub>''3''</sub>, ''A''<sub>''4''</sub>}.
| |
| | |
| Example 3: Consider ''S''= {''A''<sub>''1''</sub>, ''A''<sub>''2''</sub>, ''A''<sub>''3''</sub>, ''A''<sub>''4''</sub>} with
| |
| :''A''<sub>''1''</sub> = {a, b, c}
| |
| :''A''<sub>''2''</sub> = {b, d}
| |
| :''A''<sub>''3''</sub> = {a, b, d}
| |
| :''A''<sub>''4''</sub> = {b, d}.
| |
| | |
| The only valid SDR's are (c, b, a, d) and (c, d, a, b).
| |
| | |
| ===Standard example with men and women===
| |
| The standard example of an application of the marriage theorem is to imagine two groups; one of ''n'' men, and one of ''n'' women. For each woman, there is a subset of the men, any one of which she would happily marry; and any man would be happy to marry a woman who wants to marry him. Consider whether it is possible to pair up (in [[marriage]]) the men and women so that every person is happy.
| |
| | |
| If we let ''A''<sub>''i''</sub> be the set of men that the ''i''-th woman would be happy to marry, then the marriage theorem states that each woman can happily marry a man if and only if the collection of sets {''A''<sub>''i''</sub>} meets the marriage condition.
| |
| | |
| Note that the marriage condition is that, for any subset <math>I</math> of the women, the number of men whom at least one of the women would be happy to marry, <math>|\bigcup_{i \in I} A_i|</math>, be at least as big as the number of women in that subset, <math>|I|</math>. It is obvious that this condition is ''necessary'', as if it does not hold, there are not enough men to share among the <math>I</math> women. What is interesting is that it is also a ''sufficient'' condition.
| |
| | |
| == Graph theoretic formulation ==
| |
| | |
| When ''S'' is finite, the marriage theorem can be expressed using the terminology of [[graph theory]]. Let ''S'' = (''A''<sub>1</sub>, ''A''<sub>2</sub>, ..., ''A''<sub>n</sub>) where the ''A''<sub>i</sub> are finite sets which need not be distinct. Let the set ''X'' = {''A''<sub>1</sub>, ''A''<sub>2</sub>, ..., ''A''<sub>n</sub>} (that is, the set of names of the elements of ''S'') and the set ''Y'' be the union of all the elements in all the ''A''<sub>i</sub>. We form a finite [[bipartite graph]] ''G'':= (''X'' + ''Y'', ''E''), with bipartite sets ''X'' and ''Y'' by joining any element in ''Y'' to each ''A''<sub>i</sub> which it is a member of. A transversal (SDR) of ''S'' is an [[matching (graph theory)|''X''-saturating matching]] (a matching which covers every vertex in ''X'') of the bipartite graph ''G''.
| |
| | |
| For a set ''W'' of vertices of ''G'', let <math>N_G(W)</math> denote the [[Neighbourhood (graph theory)|neighborhood]] of ''W'' in ''G'', i.e. the set of all vertices [[Adjacent (graph theory)|adjacent]] to some element of ''W''. The marriage theorem (Hall's Theorem) in this formulation states that an ''X''-saturating matching exists [[if and only if]] for every subset ''W'' of ''X''
| |
| :<math>|W| \leq |N_G(W)|.</math>
| |
| In other words every subset ''W'' of ''X'' has enough adjacent vertices in ''Y''.
| |
| | |
| Given a finite bipartite graph ''G'':= (''X'' + ''Y'', ''E''), with bipartite sets ''X'' and ''Y'' of equal size, the marriage theorem provides necessary and sufficient conditions for the existence of a [[perfect matching]] in the graph.
| |
| | |
| A generalization to arbitrary graphs is provided by the [[Tutte theorem]].
| |
| | |
| == Proof of the graph theoretic version ==
| |
| We first prove: If a bipartite graph ''G'' = (''X'' + ''Y'', ''E'') = ''G''(''X'', ''Y'') has an ''X''-saturating matching, then |N<sub>''G''</sub>(''W'')| ≥ |''W''| for all ''W'' ⊆ ''X''.
| |
| | |
| Suppose M is a matching that saturates every vertex of ''X''.
| |
| Let the set of all vertices in ''Y'' matched by M to a given ''W'' be denoted as M(''W''). Therefore, |M(''W'')|=|''W''|, by the definition of matching.
| |
| But M(''W'') ⊆ N<sub>''G''</sub>(''W''), since all elements of M(''W'') are neighbours of ''W''.
| |
| So, |N<sub>''G''</sub>(''W'')| ≥ |M(''W'')| and hence, |N<sub>''G''</sub>(''W'')| ≥ |''W''|.
| |
| | |
| Now we prove: If |N<sub>''G''</sub>(''W'')| ≥ |''W''| for all ''W'' ⊆ X, then ''G''(''X'',''Y'') has a matching that saturates every vertex in ''X''.
| |
| | |
| Assume for contradiction that ''G''(''X'',''Y'') is a bipartite graph that has no matching that saturates all vertices of ''X''.
| |
| Let ''M'' be a maximum matching, and ''u'' a vertex not saturated by M. Consider all ''alternating paths'' (i.e., paths in ''G'' alternately using edges outside and inside M) starting from ''u''. Let the set of all points in ''Y'' connected to ''u'' by these alternating paths be ''T'', and the set of all points in ''X'' connected to ''u'' by these alternating paths (including ''u'' itself) be ''W''.
| |
| No maximal alternating path can end in a vertex in ''Y'', lest it would be an ''augmenting path'', so that we could augment M to a strictly larger matching. Thus every vertex in ''T'' is matched by M to a vertex in ''W''. Conversely, every vertex ''v'' in ''W'' \ {''u''} is matched by M to a vertex in ''T'' (namely, the vertex preceding ''v'' on an alternating path ending at ''v''). Thus, M provides a bijection of ''W'' \ {''u''} and ''T'', which implies |''W''| = |''T''| + 1. On the other hand, N<sub>''G''</sub>(''W'') ⊆ ''T'': let ''v'' in ''Y'' be connected to a vertex ''w'' in ''W''. If the edge (''w'',''v'') is in M, then ''v'' is in ''T'' by the previous part of the proof, otherwise we can take an alternating path ending in ''w'' and extend it with ''v'' getting augmenting path and showing that ''v'' is in ''T'' indeed. Hence, |N<sub>''G''</sub>(''W'')| = |''T''| = |''W''| − 1, a contradiction.
| |
| | |
| ==Marshall Hall Jr. variant==
| |
| By examining [[Philip Hall]]'s original proof carefully, [[Marshall Hall (mathematician)|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 ''S''.<ref>{{harvnb|Hall, Jr.|1986|loc=pg. 51}}</ref> This variant refines the marriage theorem and provides a lower bound on the number of SDR's that a given ''S'' may have. This variant is:<ref>{{harvnb|Cameron|1994|loc=pg.90}}</ref>
| |
| | |
| Suppose that (''A''<sub>1</sub>, ''A''<sub>2</sub>, ..., ''A''<sub>n</sub>), where the ''A''<sub>i</sub> are finite sets that need not be distinct, is a family of sets satisfying the marriage condition (MC), and suppose that |''A''<sub>i</sub>| ≥ ''r'' for ''i'' = 1, ..., ''n''. Then the number of different SDR's for the family is at least ''r'' ! if ''r'' ≤ ''n'' and ''r''(''r'' - 1) ... (''r'' - ''n'' +1) if ''r'' > ''n''.
| |
| | |
| Recall that a transversal for a family ''S'' is an ordered sequence, so two different SDR's could have exactly the same elements. For instance, the family ''A''<sub>1</sub> = {1,2,3}, ''A''<sub>2</sub> = {1,2,5} has both (1,2) and (2,1) as distinct SDR's.
| |
| | |
| ==Applications==
| |
| The theorem has many other interesting "non-marital" applications. For example, take a [[Playing card|standard deck of cards]], and deal them out into 13 piles of 4 cards each. Then, using the marriage theorem, we can show that it is always possible to select exactly 1 card from each pile, such that the 13 selected cards contain exactly one card of each rank (ace, 2, 3, ..., queen, king).
| |
| | |
| More abstractly, let ''G'' be a [[group (mathematics)|group]], and ''H'' be a finite [[subgroup]] of ''G''. Then the marriage theorem can be used to show that there is a set ''T'' such that ''T'' is an SDR for both the set of left [[coset]]s and right cosets of ''H'' in ''G''.
| |
| | |
| The marriage theorem is used in the usual proofs of the fact that an (r × n) [[Latin rectangle]] can always be extended to an ((r+1) × n) Latin rectangle when r < n, and so, ultimately to a [[Latin square]].
| |
| | |
| ==Marriage condition does not extend==
| |
| The following example, due to Marshall Hall, Jr., shows that the marriage condition (MC) will not guarantee the existence of an SDR in an infinite family in which infinite sets are allowed.
| |
| | |
| Let ''S'' be the family, ''A''<sub>0</sub> = {1, 2, 3, ...}, ''A''<sub>1</sub> = {1}, ''A''<sub>2</sub> = {2}, ..., ''A''<sub>i</sub> = {i}, ...
| |
| | |
| The marriage condition (MC) holds for this infinite family, but no SDR can be constructed.<ref>{{harvnb|Hall, Jr.|1986|loc=pg. 51}}</ref>
| |
| | |
| The more general problem of selecting a (not necessarily distinct) element from each of a collection of 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.
| |
| | |
| == Logical equivalences ==
| |
| | |
| This theorem is part of a collection of remarkably powerful theorems in combinatorics, all of which are related to each other in an informal sense in that it is more straightforward to prove one of these theorems from another of them than from first principles. These include:
| |
| | |
| * The [[König–Egerváry theorem]] (1931) ([[Dénes Kőnig]], [[Jenő Egerváry]])
| |
| * König's theorem<ref>The naming of this theorem is inconsistent in the literature. There is the result concerning matchings in bipartite graphs and its interpretation as a covering of (0,1)-matrices. {{harvtxt|Hall, Jr.|1986}} and {{harvtxt|van Lint|Wilson|1992}} refer to the matrix form as König's theorem, while {{harvtxt|Roberts|Tesman|2009}} refer to this version as the Kőnig-Egerváry theorem. The bipartite graph version is called Kőnig's theorem by {{harvtxt|Cameron|1994}} and {{harvtxt|Roberts|Tesman|2009}}.</ref>
| |
| * [[Menger's theorem]] (1927)
| |
| * The [[max-flow min-cut theorem]] (Ford–Fulkerson algorithm)
| |
| * The [[Birkhoff–Von Neumann theorem]] (1946)
| |
| * [[Dilworth's theorem]].
| |
| | |
| In particular,<ref>[http://robertborgersen.info/Presentations/GS-05R-1.pdf Equivalence of seven major theorems in combinatorics]</ref><ref>{{harvnb|Reichmeider|1984}}</ref> there are simple proofs of the implications Dilworth's theorem ⇔ Hall's theorem ⇔ König–Egerváry theorem ⇔ König's theorem.
| |
| | |
| == Notes ==
| |
| <references/>
| |
| | |
| ==References==
| |
| *{{Citation|first=Richard A.|last=Brualdi|title=Introductory Combinatorics|publisher=Prentice-Hall/Pearson|place=Upper Saddle River, NJ|year=2010|isbn=978-0-13-602040-0}}
| |
| *{{Citation|first=Peter J.|last=Cameron|title=Combinatorics: Topics, Techniques, Algorithms|publisher= Cambridge University Press|place=Cambridge|year=1994|isbn=0-521-45761-0}}
| |
| *{{Citation | last1=Dongchen | first1=Jiang | last2=Nipkow | first2=Tobias | title=Hall's Marriage Theorem | journal=The Archive of Formal Proofs | year=2010 | url=http://afp.sourceforge.net/entries/Marriage.shtml | issn=2150-914X | postscript=. Computer-checked proof.}}
| |
| *{{Citation|last=Hall, Jr.|first=Marshall|title=Combinatorial Theory|edition=2nd|publisher=John Wiley & Sons|place=New York|year=1986|isbn=0-471-09138-3}}
| |
| *{{Citation | last1=Hall | first1=Philip | author1-link=Philip Hall | title=On Representatives of Subsets | doi=10.1112/jlms/s1-10.37.26 | year=1935 | journal=J. London Math. Soc. | volume=10 | issue=1 | pages=26–30}}
| |
| *Halmos, Paul R. and Vaughan, Herbert E. "The marriage problem". American Journal of Mathematics 72, (1950). 214–215.
| |
| *{{Citation|last=Reichmeider|first=P.F.|title=The Equivalence of Some Combinatorial Matching Theorems|publisher=Polygonal Publishing House|year=1984|isbn=0-936428-09-0}}
| |
| *{{Citation|last1=Roberts|first1=Fred S.|last2=Tesman|first2=Barry|title=Applied Combinatorics|edition=2nd|publisher=CRC Press|place=Boca Raton|year=2009|isbn=978-1-4200-9982-9}}
| |
| *{{Citation|last1=van Lint|first1=J. H.|last2=Wilson|first2=R.M.|title=A Course in Combinatorics|publisher=Cambridge University Press|place=Cambridge|year=1992|isbn=0-521-42260-4}}
| |
| == External links ==
| |
| * [http://www.cut-the-knot.org/arithmetic/elegant.shtml Marriage Theorem] at [[cut-the-knot]]
| |
| * [http://www.cut-the-knot.org/arithmetic/marriage.shtml Marriage Theorem and Algorithm] at [[cut-the-knot]]
| |
| | |
| {{PlanetMath attribution|id=3059|title=proof of Hall's marriage theorem}}
| |
| | |
| [[Category:Matching]]
| |
| [[Category:Theorems in combinatorics]]
| |
| [[Category:Theorems in graph theory]]
| |
| [[Category:Articles containing proofs]]
| |