Many books say that Hall's marriage theorem is equivalent to Dilworth's theorem. Some use König's theorem to show that, but many just don't prove it at all.
Is there any simple approach to understand and later prove why this applies using set theory (without graph theory), relating the chains and anti chains from Dilworth directly to the marriage theorem and vice versa? I just want to understand it, and then try to prove it afterwards..
Best Answer
Here's a neat way to prove Dilworth's $\implies$ Hall's.
For clarity the wording of Hall's Theorem I am using is this: if there are $n$ women $w_1,\dots,w_n$, each with a set $W_i$ of men they like, there is a way to give all of them distinct husbands they like if and only if the Hall condition holds. $$ \text{Hall Condition:}\qquad\left|\bigcup_{i\in I} W_i\right|\ge |I| \quad\text{ for all } I\subseteq \{1,\dots,n\}.$$
Let $\bigcup_{i=1}^n W_i=\{m_1\dots,m_k\}$ be the men at least one woman likes. Consider the following poset, $P$: its elements are the men and women, where $m_i\le w_j$ precisely when $m_i\in W_j$, and no other comparisons hold. Then the set of men is the largest antichain precisely when the Hall condition holds, (left as exercise: consider trying to make the antichain larger when the Hall condition holds and fails). Thus, there exists a partition of $P$ into $k$ chains exactly when the Hall condition holds, which proves Hall's Theorem since such a partition is exactly a marriage assignment.
As far as I can tell, though, there isn't a nice Hall's $\implies$ Dillworth's that doesnt use Konig's as an intermediate. Both the steps Hall $\implies$ Konig's and Konig's $\implies$ Dillworth's are somewhat convoluted, so going directly seems like it must be twice as convoluted.