- Marriage theorem
In

mathematics , the**marriage theorem**(1935), usually credited to mathematicianPhilip Hall , is a combinatorial result that gives the condition allowing the selection of a distinct element from each of a collection ofsubset s.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 leftcoset s 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\; ightvertmath>,\; we\; prove\; it\; for$ leftvert\; S\; ightvert=n$.$

First suppose that we have the stronger condition$leftvertcup\; T\; ightvert\; ge\; leftvert\; T\; ightvert+1$for all $emptyset\; e\; T\; subset\; S$. Pick any $xin\; S\_n$ as the representative of $S\_n$; we must choose an SDR from$S\text{'}\; =\; left\{S\_1setminus\{x\},ldots,S\_\{n-1\}setminus\{x\}\; ight\}$.But if$\{S\_\{j\_1\}setminus\{x\},...,S\_\{j\_k\}setminus\{x\}\}\; =\; T\text{'}subseteq\; S\text{'}$then, by our assumption,$leftvertcup\; T\text{'}\; ightvert\; ge\; leftvertcup\_\{i=1\}^\{k\}\; S\_\{j\_i\}\; ightvert-1\; ge\; k$.By the already-proven case of the theorem for $S\text{'}$ 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\text{'}subseteq\; Tsubset\; S$ we have$leftvertcup\; T\text{'}\; ightvertgeleftvert\; T\text{'}\; 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\text{'}subseteq\; Ssetminus\; T$, even after discarding elements of $cup\; T$ there remain enough elements in $cup\; T\text{'}$: we must prove$leftvertcup\; T\text{'}\; setminus\; cup\; T\; ightvert\; ge\; leftvert\; T\text{'}\; ightvert$.

But

$leftvertcup\; T\text{'}\; setminus\; cup\; T\; ightvert$

$=\; leftvertigcup(Tcup\; T\text{'})\; ightvert\; -\; leftvertcup\; T\; ightvert\; ge\; leftvert\; Tcup\; T\text{'}\; ightvert\; -\; leftvert\; T\; ightvert$

$=\; leftvert\; T\; ightvert\; +\; leftvert\; T\text{'}\; ightvert\; -\; leftvert\; T\; ightvert\; =\; leftvert\; T\text{'}\; ightvert$,

using the disjointness of $T$ and $T\text{'}$, 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 completematching 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 aperfect 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 enoughadjacent vertices in "T".A generalization to arbitrary graphs is provided by

Tutte theorem .**A more general statement**Let G be a

bipartite graph , BIP^{N}(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

* TheKonig-Egervary theorem (1931) (Dénes Kőnig ,Jenő Egerváry )

*Menger's theorem (1927)

* The Max-Flow-Min-Cut theorem (Ford-Fulkerson Algorithm)

* TheBirkhoff-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*] atcut-the-knot

* [*http://www.cut-the-knot.org/arithmetic/marriage.shtml Marriage Theorem and Algorithm*] atcut-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