# 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} |}$

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 .

## literature

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.