Marriage theorem

Marriage theorem

In mathematics, the marriage theorem (1935), usually credited to mathematician Philip Hall, is a combinatorial result that gives the condition allowing the selection of a distinct element from each of a collection of subsets.

Formally, let "S" = {"S""1", "S""2", ... } be a (not necessarily countable) collection of finite subsets of some larger set "M". A "transversal" for "S", also known as a "system of distinct representatives" for "S", or as used here, an "SDR", is a set "X" = {"x""1", "x""2", ...} of distinct elements of "M" (where |"X"| = |"S"|) and with the property that for all "i", "x""i" is in "S""i".

The marriage condition for "S" is that, for any subcollection "T" = {"T""i" } of "S",

:|igcup T_i| ge |T|(i.e. the set created by the union of some n elements, which are themselves subsets of "M", in "S" must itself have cardinality of at least n)

The marriage theorem (more well known as Hall's Theorem) then states that there exists a system of distinct representatives "X" = {"x""i"} if and only if "S" meets the marriage condition.

Example: "S""1" = {1, 2, 3}"S""2" = {1, 4, 5}"S""3" = {3, 5}

For this set "S" = {"S""1", "S""2", "S""3"}, a valid SDR would be {1, 4, 5}. (Note this is not unique: {2, 1, 3} works equally well)

The standard example of an application of the marriage theorem is to imagine two groups of "n" men and women. Each woman would happily marry some subset of the men; 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 "M""i" 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 {"M""i"} meets the marriage condition.

Note that the marriage condition is that, for any subset I of the women, the number of men whom at least one of the women would be happy to marry, |igcup _{i in I} T_i|, be at least as big as the number of women in that subset, |I| = |{T_i: i in I}|. It is obvious that this condition is "necessary", as if it does not hold, there are not enough men to share among the I women. What is interesting is that it is also a "sufficient" condition.

The theorem has many other interesting "non-marital" applications. For example, take a 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 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, and "H" be a finite subgroup of "G". Then the marriage theorem can be used to show that there is a set "X" such that "X" is an SDR for both the set of left cosets and right cosets of "H" in "G".

This can also be applied to the problem of Assignment: Given a set of n employees, fill out a list of the jobs each of themwould be able to perform. Then, we can give each person a job suited to their abilities if, and only if, for every value of k (1...n), the union of any k of the lists contains at least k jobs.

The more general problem of selecting a (not necessarily distinct) element from each of a collection of sets is permitted in general only if the axiom of choice is accepted.

Proof

We prove the finite case of Hall's marriage theorem by induction on leftvert S ightvert, the size of S. The infinite case follows by a standard compactness argument.

The theorem is trivially true for vert Svert=0.

Assuming the theorem true for all leftvert S ightvert, we prove it for leftvert S ightvert=n.

First suppose that we have the stronger condition leftvertcup T ightvert ge leftvert T ightvert+1for all emptyset e T subset S. Pick any xin S_n as the representative of S_n; we must choose an SDR from S' = left{S_1setminus{x},ldots,S_{n-1}setminus{x} ight}.But if {S_{j_1}setminus{x},...,S_{j_k}setminus{x}} = T'subseteq S'then, by our assumption, leftvertcup T' ightvert ge leftvertcup_{i=1}^{k} S_{j_i} ightvert-1 ge k.By the already-proven case of the theorem for S' we see that we can indeed pick an SDR for S.

Otherwise, for some emptyset e T subset S we have the "exact" size leftvertcup T ightvert=leftvert T ightvert.Inside T itself, for any T'subseteq Tsubset S we have leftvertcup T' ightvertgeleftvert T' ightvert,so by an already-proven case of the theorem we can pick an SDR for T.

It remains to pick an SDR for Ssetminus T which avoids all elements of cup T (these elements are in the SDR for T). To use the already-proven case of the theorem (again) and do this, we must show that for any T'subseteq Ssetminus T, even after discarding elements of cup T there remain enough elements in cup T': we must prove leftvertcup T' setminus cup T ightvert ge leftvert T' ightvert.

But

leftvertcup T' setminus cup T ightvert

= leftvertigcup(Tcup T') ightvert - leftvertcup T ightvert ge leftvert Tcup T' ightvert - leftvert T ightvert

= leftvert T ightvert + leftvert T' ightvert - leftvert T ightvert = leftvert T' ightvert,

using the disjointness of T and T', and keeping in mind we are considering the case where leftvertcup T ightvert=leftvert T ightvert. So by an already-proven case of the theorem, Ssetminus T does indeed have an SDR which avoids all elements of cup T,

Q.E.D.

Corollary

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 vert Svertleq vert N(S)vert for every subset Ssubset V_1.

Graph theory

The marriage theorem has applications in the area of graph theory. Formulated in graph theoretic terms the problem can be stated as:

Given a bipartite graph "G":= ("S" + "T", "E") with two equally sized partitions "S" and "T", does there exist a perfect matching?

The marriage theorem provides the answer:

Let N_G(X) denote the neighborhood of "X" in "G". The Marriage theorem (Hall's Theorem) for Graph theory states that a perfect matching exists if and only if for every subset "X" of "S" :|X| leq |N_G(X)|In other words every subset "X" has enough adjacent vertices in "T".

A generalization to arbitrary graphs is provided by Tutte theorem.

A more general statement

Let G be a bipartite graph, BIPN(X,Y), with X and Y not necessarily equally sized. Then G contains a matching of X into Y iff Hall's condition is satisfied for X.

If we denote the set of all vertices adjacent to at least one member of A by Г(A) (previously N_G(A)), then Hall's condition is that for all subsets A of X, |Г(A)| ge |A|.

Logical equivalences

This theorem is part of a collection of remarkably powerful theorems in combinatorics, all of which are logically equivalentFact|date=September 2008. These include:

* König's theorem
* The Konig-Egervary theorem (1931) (Dénes Kőnig, Jenő Egerváry)
* Menger's theorem (1927)
* The Max-Flow-Min-Cut theorem (Ford-Fulkerson Algorithm)
* The Birkhoff-Von Neumann theorem (1946)
* Dilworth's theorem

References

* [http://robertborgersen.info/Presentations/GS-05R-1.pdf Equivalence of seven major theorems in combinatorics]

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


Wikimedia Foundation. 2010.

См. также в других словарях:

  • Hall's marriage theorem — In mathematics, Hall s marriage theorem is a combinatorial result that gives the condition allowing the selection of a distinct element from each of a collection of finite sets. It was proved by Philip Hall (1935). Contents 1 Definitions and …   Wikipedia

  • Dilworth's theorem — In mathematics, in the areas of order theory and combinatorics, Dilworth s theorem characterizes the width of any finite partially ordered set in terms of a partition of the order into a minimum number of chains. It is named for the mathematician …   Wikipedia

  • Tutte theorem — In the mathematical discipline of graph theory the Tutte theorem, named after William Thomas Tutte, is a characterization of graphs with perfect matchings. It is a generalization of the marriage theorem and is a special case of the Tutte Berge… …   Wikipedia

  • König's theorem (graph theory) — In the mathematical area of graph theory, König s theorem describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. Setting A graph is bipartite if its vertices can be partitioned into …   Wikipedia

  • List of combinatorics topics — This is a list of combinatorics topics.A few decades ago it might have been said that combinatorics is little more than a way to classify poorly understood problems, and some standard remedies. Great progress has been made since 1960.This page is …   Wikipedia

  • List of theorems — This is a list of theorems, by Wikipedia page. See also *list of fundamental theorems *list of lemmas *list of conjectures *list of inequalities *list of mathematical proofs *list of misnamed theorems *Existence theorem *Classification of finite… …   Wikipedia

  • List of mathematics articles (M) — NOTOC M M estimator M group M matrix M separation M set M. C. Escher s legacy M. Riesz extension theorem M/M/1 model Maass wave form Mac Lane s planarity criterion Macaulay brackets Macbeath surface MacCormack method Macdonald polynomial Machin… …   Wikipedia

  • Matching (graph theory) — In the mathematical discipline of graph theory, a matching or independent edge set in a graph is a set of edges without common vertices. It may also be an entire graph consisting of edges without common vertices. Covering packing dualities… …   Wikipedia

  • Graph factorization — Not to be confused with Factor graph. 1 factorization of Desargues graph: each color class is a 1 factor …   Wikipedia

  • Philip Hall — Infobox Scientist name = Philip Hall caption = Philip Hall birth date = birth date|1904|4|11|df=y birth place = Hampstead, London, England death date = death date and age|1982|12|30|1904|4|11|df=y death place = Cambridge, England residence =… …   Wikipedia


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»