Marriage rate

The marriage theorem , or Hall's theorem , named after Philip Hall , is a mathematical theorem from combinatorics or from the theory of finite sets from 1935. It is the starting point of the matching theory in graph theory .

Problem

${\displaystyle 1\in A_{1}}$, , And is a possible choice. ${\displaystyle 2\in A_{2}}$ ${\displaystyle 5\in A_{3}}$ ${\displaystyle 7\in A_{4}}$

The sets violate the Hall conditions, since their union contains only 2 elements. ${\displaystyle A_{1},A_{2},A_{3}}$

Given are a natural number , a finite set and a finite number of subsets of , which do not necessarily all have to be different. Then the question is: ${\displaystyle n}$ ${\displaystyle X}$ ${\displaystyle A_{1},\ldots ,A_{n}}$ ${\displaystyle X}$

Is there a "representative system" ( English system of distinct Representatives ), that is, elements such that all are different? ${\displaystyle x_{i}\in A_{i}}$   ${\displaystyle (i=1,\ldots ,n)}$ ${\displaystyle x_{1},\ldots ,x_{n}}$

Or more generally:

Given a finite index set and a family of finite sets. Then the question is: ${\displaystyle I}$ ${\displaystyle {\mathcal {A}}=(A_{i})_{i\in I}}$

Exists for an " injective selection function " ${\displaystyle {\mathcal {A}}}$

${\displaystyle a\colon I\to \bigcup _{i\in I}A_{i}}$,

so that applies to all ? ${\displaystyle a(i)\in A_{i}}$ ${\displaystyle i\in I}$

interpretation

The following interpretation led to the widespread term marriage sentence :

Given are a finite number of women willing to marry and a finite number of men who are friends with these women. For every woman is the number of men befriended. ${\displaystyle I}$ ${\displaystyle X}$ ${\displaystyle i\in I}$ ${\displaystyle A_{i}\subseteq X}$ ${\displaystyle i}$

Then the question is:

Can women marry men in such a way that every woman marries one of the men she is friends with without violating the monogamy rule? An illustration of the marriage rate is found in the article by Konrad Jacobs in the Selecta Mathematica I .

Necessary condition

Such a marriage requires that every woman choose a man to marry without two women marrying the same man. This must apply not only to all women, but also to any subset. So it is obviously necessary that women are always friends with at least men. ${\displaystyle i}$ ${\displaystyle x_{i}\in A_{i}}$ ${\displaystyle k}$ ${\displaystyle k}$

This means: for every subset there must always be at least elements in the union . ${\displaystyle I_{0}\subseteq I}$ ${\displaystyle \bigcup _{i\in I_{0}}A_{i}}$ ${\displaystyle |I_{0}|}$

The existence of a selection of the type required we exactly get the following necessary condition, which is also called the Hall condition or hallsche condition ( english Hall's condition is called):

For each subset is . ${\displaystyle I_{0}\subseteq I}$ ${\displaystyle |\bigcup _{i\in I_{0}}A_{i}|\geq |I_{0}|}$

Marriage rate

The marriage theorem now states that the Hall condition for the existence of a selection is not only necessary but also sufficient:

There were , and as described above. Then the following statements are equivalent: ${\displaystyle I}$ ${\displaystyle {\mathcal {A}}}$

• It exists for an injective selection function ${\displaystyle {\mathcal {A}}}$

${\displaystyle a\colon I\to \bigcup _{i\in I}A_{i},\quad i\mapsto x_{i}\in A_{i}}$.

• The Hall condition is met.

Evidence and Related Sentences

A direct proof can be given by induction on the number of sets . Such proof can be found in the Proofs from THE BOOK by Martin Aigner and Günter Ziegler . The sentence can also be traced back directly to Dilworth's theorem . As can be seen, the marriage theorem , the Dilworth theorem and the König theorem can easily be derived from each other. ${\displaystyle |I|}$ ${\displaystyle A_{i}}$

Graph theoretical representation

The blue edges form a matching in which all nodes from A occur.

Hall's marriage theorem can be represented graphically as follows. Let it be a bipartite graph with bipartition . A matching is a set of different edges that no nodes of the graph have in common. For a subset, let the set of all points that are adjacent to, which are necessarily a subset of because of bipartism . The question of a matching in which all nodes occur is the question of a selection of pairs of different nodes for all of them . The marriage rate in this context is: ${\displaystyle G=(V,E)}$ ${\displaystyle \{A,B\}}$ ${\displaystyle S\subset A}$ ${\displaystyle N(S)}$ ${\displaystyle S}$ ${\displaystyle B}$ ${\displaystyle a\in A}$ ${\displaystyle b_{a}\in N(\{a\})}$ ${\displaystyle a\in A}$

For a bipartite graph with bipartition , the following statements are equivalent: ${\displaystyle \{A,B\}}$

• There is a matching in which every node from occurs. ${\displaystyle A}$
• The following applies to all subsets . ${\displaystyle S\subseteq A}$ ${\displaystyle |N(S)|\geq |S|}$
• There is an injective function with a domain (which is a possible injective selection function as described in the problem definition chapter ). ${\displaystyle f\subseteq E}$ ${\displaystyle A}$

Whether such a matching exists can be answered with the help of the network flow model .

Generalizations

In the literature on the marriage rate there are a large number of generalizations and expansions under different conditions:

Generalization according to Philip A. Ostrand

This generalization ( theorem of Ostrand ) tightens the marriage rate in such a way that a lower bound is given here for estimating the number of representative systems with which the marriage rate results directly:

Let a natural number and a finite family of finite sets be given. This is arranged in ascending order in the following sense : ${\displaystyle n}$ ${\displaystyle {\mathcal {A}}=(A_{1},\ldots ,A_{n})}$

${\displaystyle |A_{1}|\leq |A_{2}|\leq \ldots \leq |A_{n}|}$

The number of representative systems of will be denoted by. ${\displaystyle {\mathcal {A}}}$ ${\displaystyle v_{\mathcal {A}}}$

Then:

If the Hall condition is met , then ${\displaystyle {\mathcal {A}}}$

${\displaystyle v_{\mathcal {A}}\geq \prod _{i=1}^{n}{\operatorname {max} \left(1,\ \left|A_{i}\right|-i+1\right)}}$.

The connection to the marriage rate results from the observation that applies to throughout . Ostrand's theorem says in particular that if the Hall condition is valid, the number of substitute systems must be at least , so that in this case a substitute system exists. ${\displaystyle i=1,\ldots ,n}$ ${\displaystyle {\operatorname {max} (1,|A_{i}|-i+1)}>0}$ ${\displaystyle 1}$

As the Dutch mathematician Jacobus Hendricus van Lint was able to show, the above limit is the best possible if only the numbers are known. ${\displaystyle |A_{i}|}$

Generalization according to Rado

→ Main article : Rado's theorem

This generalization, which goes back to Richard Rado , connects the marriage theorem with matroid theory . The starting point here is the following question:

Under what conditions does a “representative system” exist for a given matroid and a given finite family of subsets such that the subset is “independent”? ${\displaystyle {\mathcal {M}}=(X;{\mathcal {U}})}$ ${\displaystyle {\mathcal {A}}=(A_{i})_{i\in I}}$ ${\displaystyle X}$ ${\displaystyle (a_{i})_{i\in I}}$ ${\displaystyle A=\{a_{i}:i\in I\}}$

Such a subset is also called an "independent transversal". ${\displaystyle A}$

In a nutshell, the question in question should be asked as follows:

Under which conditions does a given matroid have an independent transversal for a given finite family of subsets ? ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {A}}}$

The answer to this question is given by Rado's theorem , which says:

${\displaystyle {\mathcal {M}}}$has an independent transversal if and only if the inequality is satisfied for each subfamily . ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {A}}_{H}=(A_{i})_{i\in H}}$   ${\displaystyle (H\subseteq I)}$ ${\displaystyle \rho (\bigcup _{i\in H}A_{i})\geq |H|}$

The last condition is called Rados condition ( English Rado’s condition ) or Hall-Rado condition ( English Hall-Rado condition ) or similar. It means that for each the associated union includes an independent subset with at least elements . From here one arrives at the Hall condition by taking the number function as a rank function , which assigns the number of its elements to each subset . In the matroid belonging to the number function, all subsets of are independent. Thus the marriage sentence proves to be a special case of Rado's theorem . ${\displaystyle H\subseteq I}$ ${\displaystyle |H|}$ ${\displaystyle |\cdot |\colon {\mathcal {P}}(X)\to \mathbb {N} _{0}}$ ${\displaystyle T\subseteq X}$ ${\displaystyle |T|}$ ${\displaystyle X}$

Extension to the infinite fall

There are extended versions of the marriage theorem and Rado's theorem (and also of Dilworth's theorem ), which (among other things) include the case that the basic set is infinite . The proofs of these transfinite versions , however, usually use Zorn's lemma or Tychonoff's theorem as a decisive aid, i.e. start from the axiom of choice .

Web links

Wikiversity: A Proof of the Marriage Theorem in a Discrete Mathematics  Course - Course Materials

literature

• Martin Aigner, Günter M. Ziegler : Proofs from THE BOOK . Springer Verlag, Berlin (inter alia) 1991, ISBN 3-540-63698-6 .
• Martin Aigner: Combinatorics II: Matroids and transversal theory (=  university text ). Springer Verlag, Berlin ( inter alia ) 1976, ISBN 3-540-07949-1 ( MR0460127 ).
• Heinz-Richard Halder, Werner Heise : Introduction to combinatorics . Hanser Verlag, Munich ( inter alia ) 1976, ISBN 3-446-12140-4 ( MR0498160 ).
• Konrad Jacobs (Ed.): Selecta Mathematica I (=  Heidelberg Pocket Books . Volume 49 ). Springer-Verlag, Berlin / Heidelberg / New York 1969, p. 103-141 .
• Konrad Jacobs, Dieter Jungnickel: Introduction to combinatorics (=  de Gruyter textbook ). 2nd, completely revised and expanded edition. de Gruyter, Berlin (et al.) 2004, ISBN 3-11-016727-1 .
• Dieter Jungnickel : Transversal Theory (=  mathematics and its applications in physics and technology . Volume 39 ). Academic publishing company Geest & Portig K.-G., Leipzig 1982 ( MR0706076 ).
• L. Lovász , MD Plummer: Matching Theory (=  North-Holland Mathematics Studies . Volume 121 ). North-Holland, Amsterdam ( inter alia ) 1986, ISBN 0-444-87916-1 ( MR0859549 ).
• Heinz Lüneburg : combinatorics (=  elements of mathematics from a higher point of view . Volume 6 ). Birkhäuser Verlag, Basel / Stuttgart 1971, ISBN 3-7643-0548-7 ( MR0335267 ).
• Leonid Mirsky : Transversal Theory (=  North-Holland Mathematics Studies . Volume 121 ). Academic Press, New York / London 1971, ISBN 0-12-498550-5 ( MR0282853 ).
• L. Mirsky , Hazel Perfect: Systems of Representatives . In: J. Math. Anal. Appl . tape 15 , 1966, pp. 520-568 ( sciencedirect.com ; MR0204300 ).
• Philip. A. Ostrand: Systems of distinct representatives, II . In: J. Math. Anal. Appl. tape 32 , 1970, pp. 1-4 ( ac.els-cdn.com [PDF]). MR0280385 .
• R. Rado : A theorem on independence relations . In: Quart. J. Math. (Oxford) . tape 13 , 1942, pp. 83-89 ( qjmath.oxfordjournals.org [PDF] MR0008250 ).
• Philip F. Reichmeider: The Equivalence of Some Combinatorial Matching Theorems . Polygonal Publishing House, Washington NJ 1984, ISBN 0-936428-09-0 ( MR0781348 ).
• DJA Welsh : Matroid Theory (=  LMS Monographs . Volume 8 ). Academic Press, London (et al.) 1976, ISBN 0-12-744050-X ( MR0427112 ).
• Hermann Weyl : Almost periodic invariant vector sets in a metric vector space . In: Amer. J. Math . tape 71 , 1949, pp. 178-205 , JSTOR : 2372104 ( MR0028530 ).

References and comments

1. ^ P. Hall: On representation of subsets. Quart. J. Math. (Oxford) 10, 1935, pp. 26-30.
2. ↑ ^{a b c} Aigner-Ziegler: pp. 134-136.
3. ↑ The term "marriage set" ( English marriage theorem ) and the interpretation associated are in the technical literature on Hermann Weyl returned; see. Jacobs-Jungnickel: pp. 23, 393. Weyl explicitly mentions the question at issue as the marriage problem ; see. Weyl: Amer. J. Math. Band 71 , p. 202 ff .
4. ↑ Jacobs: Selecta Mathematica I . S. 103 ff .
5. ↑ ^{a b} Halder-Heise: pp. 145–149.
6. ↑ This is the number of elements of . ${\displaystyle |I_{0}|}$ ${\displaystyle I_{0}}$
7. ↑ Jungnickel, Konrad Jacobs: p. 27 ff.
8. ^ Winfried Hochstättler: Algorithmische Mathematik , Springer-Verlag (2010), ISBN 3-642-05421-8 , sentence 4.36.
9. ^ Ostrand: J. Math. Anal. Appl. tape 32 , p. 1-4 .
10. ↑ The necessity of fulfilling the Hall condition is seen as evident here.
11. ↑ So this is the number of injective selection functions for . Here is generally, if nothing is further provided . ${\displaystyle a\colon \{1,\ldots ,n\}\to A_{1}\cup \ldots \cup A_{n}}$ ${\displaystyle {\mathcal {A}}=(A_{1},\ldots ,A_{n})}$ ${\displaystyle v_{\mathcal {A}}=0}$
12. ↑ Halder-Heise: p. 149.
13. ↑ is the given finite basic set in which all are contained and is the associated system of independent subsets . ${\displaystyle X}$ ${\displaystyle A_{i}}$ ${\displaystyle {\mathcal {U}}}$
14. ↑ If one establishes the connection with the injective selection function described above , then is , where the subset is exactly the - image set of , to which it is in this way in a reversibly unique relationship. ${\displaystyle a\colon I\to \bigcup _{i\in I}A_{i}}$ ${\displaystyle (a_{i})_{i\in I}=(a(i))_{i\in I}}$ ${\displaystyle A}$ ${\displaystyle a}$ ${\displaystyle I}$
15. ^ Rado: Quart. J. Math. (Oxford) . tape 13 , p. 83 ff .
16. ↑ Aigner: p. 246 ff.
17. ↑ Mirsky: p. 93 ff.
18. ↑ Welsh: p. 97 ff.
19. ↑ is the associated rank function . ${\displaystyle \rho \colon {\mathcal {P}}(X)\to \mathbb {N} _{0}}$ ${\displaystyle {\mathcal {M}}}$
20. ↑ Welsh: p. 389 ff.
21. ↑ See also Rado's selection principle .