# (Extended) Hall's Marriage Theorem from Dilworth's Theorem

This question comes from Exercises III.4.5 and III.4.6 of Bourbaki's Set Theory. They are about using Dilworth's Theorem to prove Hall's Marriage Theorem (did it) and a mild extension of it (can't do it).

Dilworth's Theorem: Let $E$ be a finite ordered set and $k$ be the maximal number of elements of an antichain in $E$. Then there exists a partition of $E$ into $k$ totally ordered sets.

Hall's Marriage Theorem: Let $E$ and $F$ be two finite sets and let $x\rightarrow A(x)$ be a mapping of $E$ into $\mathfrak{P}(F)$ such that $\text{Card}(\bigcup_{x\in H}A(x))\geq\text{Card}(H)$ for any subset $H$ of $E$. Then there exists an injection $f$ of $E$ into $F$ such that $f(x)\in A(x)$ for each $x\in E$.

To prove it, one defines an ordering on the disjoint union of $E$ and $F$ such that $x>y$ if and only if $x\in E$ and $y\in F$ and $y\in A(x)$. It is easy to see that $F$ is an antichain and that there is no antichain with more elements than $F$. So there exists a partition of $E\sqcup F$ into $\text{Card}(F)$ totally ordered sets, which are necessarily either one-point subsets of $F$ or pairs $\{x,y\}$ such that $y\in A(x)$. Those pairs define the asserted injection.

Hall's Marriage Theorem (Extended Version): In the setting of above, suppose additionally that $G$ is a subset of $F$ and for each $L\subset G$, $\text{Card}(\{x\in E|A(x)\cap L\neq\emptyset\})\geq\text{Card}(L)$. Then we can choose $f$ as above with the additional property $G\subset f(E)$.

The proof is sketched by Bourbaki as follows: Consider the disjoint union of $G$, $F$, and $E$, which I denote here as $(\{1\}\times G)\cup(\{2\}\times F)\cup(\{3\}\times E)$, and define an ordering on it by setting as only relations

• $(1,z)<(2,y)$ if and only if $z=y$
• $(1,z)<(3,x)$ if and only if $z\in A(x)$
• $(2,y)<(3,x)$ if and only if $y\in A(x)$

Then apply Dilworth's Theorem.

The problem is that I don't quite know how. The greatest number of elements in an antichain is again $\text{Card}(F)$. So we get a partition of $G\sqcup F\sqcup E$ into $\text{Card}(F)$ totally ordered sets. Again, each of those sets contains exactly one element of $F$, at most one of $E$, and at most one of $G$. This way we can define an injection $f$ as before by defining $f(x)$ to be the element of $F$ which lies in the same set of the partition as $x$, but for $G\subset f(E)$ to hold, every set of the partition which contains an element of $G$ would have to contain an element of $E$ as well. But that's obviously not true for all partitions of $G\sqcup F\sqcup E$ into $\text{Card}(F)$ totally ordered sets.

So I think that either one has to find a more sophisticated way of defining $f$ from a given partition or one has to modify the order relation before applying Dilworth's Theorem, somehow using the condition on the subsets of $G$. Does someone see a way to finish the proof?

• Not a helpful comment, but: I had no idea that such actually useful things were discussed in Bourbaki's Set Theory (albeit in the problems). Maybe I should check it out after all... – Pete L. Clark Apr 7 '11 at 22:06
• This may be in Philip Reichmeider's book, The Equivalence of Some Combinatorial Matching Theorems. The book discusses Dilworth, Hall, Konig, Menger, max-flow-min-cut, etc., etc. Sadly, it's out of print. – Gerry Myerson Apr 20 '11 at 3:58

To finish the proof, you must also define an injection g of G into E, using the condition on the subsets of G and Dilworth's Theorem.

Then for each element a∈G \ f(E), you can redefine f so that af(E), using the injection g as follows :

Build a set of elements a0, a1, ... of G so that a0 = a and ai = g(f(ai-1)) for i>0.

Let j be the smallest integer so that aj does not belong to G (its existence has to be proved, though).

Redefine f so that f(g(ai)) = ai for each i < j. The new f is still an injection of E into F such that f(x) ∈ A(x) for each x ∈ E, and besides, af(E).

Repeat this for each element of G \ f(E) and the problem is solved.

Hope I did not go wrong somewhere. Excuse my poor english, I'm French !

Regards

Alexis

• Wow! I didn't expect an answer on this one anymore. Thank you! However, it might take a while until I find the time to take up the problem again and give you feedback. – Stefan Jun 29 '11 at 20:08
• Perfect, thank you. It should be $f(g(a_{i-1}))$ instead of $g(f(a_{i-1}))$. This answer is readable enough, but just in case you didn't know: you can use LaTeX on this site by simply enclosing your formulas in dollar signs. – Stefan Jul 4 '11 at 10:34
• "It should be $f(g(ai−1))$ instead of $g(f(ai−1))$" You're right ! – Alexis Jul 4 '11 at 13:05
• Sorry to bother you again. The structure of this site is a little different from the usual message board. Normally, each user posts at most one answer per question. Further discussion is exclusively done in the comments. In particuĺar, the answer you posted below should be a comment. Just to let you know. – Stefan Jul 4 '11 at 20:43