2
$\begingroup$

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..

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ robertborgersen.info/Presentations/GS-05R-1.pdf gives a number of proofs around all these theorems. $\endgroup$
    – Mitch
    Sep 25 '14 at 16:28
  • $\begingroup$ How is this relation reflexive? How is transitive? And why is antisimetric? $\endgroup$
    – Aqua
    Jan 18 '18 at 13:05
  • $\begingroup$ @JohnWatson Ok, you also need to add the realtions $m_i\le m_i$ and $w_j\le w_j$ for reflexivity. Antisymmetry holds since $a\le b$ implies $a$ is at least as "manly" as $b$, so $a\le b$ and $b\le a$ imply $a$ and $b$ have the same gender, which only happens when $a=b$. You can also work out why transitivity holds. $\endgroup$ Jan 18 '18 at 14:06
  • $\begingroup$ Here is the correct relation: $a\le b$ holds when $a=b$, or when $a$ is a man and $b$ is a woman such that $b$ likes $a$. Note that sometimes you can have $a\le b$ and $b\le a$, but only when $a=b$. Take a couple small examples and draw out the Hasse diagram to understand why this is a valid poset. @JohnWatson $\endgroup$ Jan 18 '18 at 14:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.