Dilworth's theorem states that given a finite partially ordered set, the length of the maximal anti-chain, is equal to the minimal number of chains needed to partition the set.

I need to prove that the Min-cut Max-flow theorem implies Dilworth's Theorem. I've tried building the flow graph, defining the edges according to the partial order, but I can't seem to find the real catch. I'm not sure what capacity to give to each edge, and which vertices to connect to the special vertices s and t (If I'm in the right direction at all...). Any help?



These notes contain a proof. The digraph used in this proof is a little more complicated than the one that you have in mind: each point of the partial order corresponds to two vertices of the digraph.

Let $\langle P,\preceq\rangle$ be the partially ordered set; I’ll write $p\prec q$ to indicate that $p\preceq q$ and $p\ne q$. For each $p\in P$ the digraph $D$ will have two vertices, $p^-$ and $p^+$; in addition, it will have a source vertex $s$ and a sink vertex $t$. For each $p\in P$, $D$ has edges $\langle s,p^-\rangle$ and $\langle p^+,t\rangle$; in addition, for each$p,q\in P$ with $p\prec q$ it has $\langle p^-,q^+\rangle$. Each edge has capacity $1$.

Let $f$ be a maximal flow in $D$, and let $\langle S,T\rangle$ be a minimal cut constructed by the Ford-Fulkerson algorithm. Note that every path from $s$ to $t$ has the form $s\to p^-\to q^+\to t$ for some $p,q\in P$ with $p\prec q$; thus $|f|$ is the number of $p\in P$ such that $f(s,p^-)=1$ there is a $q\in P$ such that $f(p^-,q^+)=1$. Let $C=\{p\in P:f(s,p^-)=0\}$; for future reference note that $|C|=|P|-|f|$.

If $p\in P\setminus C$, then $f(s,p^-)=1$, and there must therefore be a unique ‘successor’ $\sigma(p)\in P$ such that $f(p^-,\sigma(p)^+)=1$, and hence $p\prec\sigma(p)$. Thus, for each $p\in P$ there is a well-defined chain $$p=p_0\prec p_1\prec\ldots\prec p_n\in C$$ in $P$ such that $p_{k+1}=\sigma(p_k)$ for $k=0,\dots,n-1$. ($P$ is finite, so each chain must terminate, and the elements of $C$ are the only elements without successors.) For $p\in P\setminus C$ let $\xi(p)$ be the unique element of $C$ at which the chain from $p$ terminates, and let $\xi(p)=p$ for $p\in C$; then $$\Big\{\{p\in P:\xi(p)=q\}:q\in C\Big\}$$ partitions $P$ into $|C|$ chains. To complete the proof we must show that $P$ also has an antichain of cardinality $|C|$.

The desired antichain is $A=\{p\in P:p^-\in S\text{ and }p^+\in T\}$. Proving that it’s an antichain isn’t too hard. Suppose that $p,q\in A$ with $p\ne q$. Then $p^-\in S$ and $q^+\in T$, so $f(p^-,q^+)\ne0$: either $\langle p^-,q^+\rangle$ isn’t an edge of $D$ at all, or $f(p^-,q^+)=1$, and I leave it to you to show that the latter is impossible: it would unbalance the flow at $p^-$. (The argument here uses the hypothesis that the minimal cut was constructed using the F-F algorithm.) It follows that $p\not\preceq q$, and by symmetry (or a similar argument) $q\not\preceq p$. Thus, $A$ is an antichain.

The last step is to show that the edges contributing capacity towards $c(S,T)$ are preciesly the edges $\langle s,p^-\rangle$ and $\langle p^+,t\rangle$ such that $p\notin A$; this also uses the hypothesis that the minimal cut was constructed using the F-F algorithm, to show that there are no edges of the form $\langle p^-,q^+\rangle$ with $p^-\in S$ and $q^+\in T$.

Once you’ve worked out these details, you’ll have shown that $c(S,T)=|P|-|A|$ and hence that $|A|=|P|-c(S,T)=|P|-|f|=|C|$, as desired.


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.