Skip to the content

Math 2.0

Combinatorics Matchings and covers Theorem

Hall's marriage theorem

Statement

Let $\mathcal{F} = (S_1, \dots, S_n)$ be a finite family of finite sets. A transversal of $\mathcal{F}$ is an injective function $f : \{1, \dots, n\} \to \bigcup_i S_i$ with $f(i) \in S_i$ for every $i$ . Then $\mathcal{F}$ has a transversal if and only if $\left| \bigcup_{i \in I} S_i \right| \ge |I|$ for every $I \subseteq \{1, \dots, n\}$ .

Remarks

The condition on all subfamilies is the marriage condition. It is necessary, because a transversal $f$ maps $I$ injectively into $\bigcup_{i \in I} S_i$ . A transversal is also called a system of distinct representatives. The sets $S_i$ may repeat in the family. The theorem is equivalent to Hall's theorem for bipartite graphs.

History

Philip Hall proved the theorem in 1935. The name marriage theorem comes from a 1950 paper by Halmos and Vaughan.

Further reading

Web https://en.wikipedia.org/wiki/Hall's_marriage_theorem, Statement

About this page

Tag	`08WCB90WND`
URI	`m2://08WCB90WND`
Kind	statement, theorem
Writing	W0 stub
MSC	05D15
Status	This copy of the site has no build data. Run `m2 status 08WCB90WND`.
Same as	Wikidata Q536640 Wikipedia Hall's marriage theorem

Markdown · JSON · Edit on GitHub

What this page needs for W1

edge uses out: each definition that the statement needs (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.