Dilworth's theorem states that for any partial order, the size of the largest antichains is the size of the smallest chain partitions. Mirsky's theorem states that for any partial order, the size of the longest chains is the size of the smallest antichain partitions. Wikipedia says that those theorems are dual, which is clear from what they state, but they do not have the same proofs: the proof of Dilworth's theorem is an induction whereas Mirsky's theorem has a very elegant proof. Are there dual proofs of those two results, or a way to "see" the duality between chains and antichains that those results suggest? (Edit: I am interested in the case of finite partial orders.)
[Math] How to understand the duality between Dilworth’s theorem and Mirsky’s theorem
intuitionorder-theory
Best Answer
I'm having a very limited amount of time for m.se right now, but let me give the relevant link:
Thomas Britz, Sergey Fomin, Finite posets and Ferrers shapes.
There are three versions of the paper: an arXiv one ( http://arxiv.org/abs/math/9912126 ), a PS file on Fomin's webpage ( http://www.math.lsa.umich.edu/~fomin/Papers/posetshapes.ps ) and a published version in Adv in Math ( http://www.sciencedirect.com/science/article/pii/S0001870800919662 ). The published one seems to have the most mistakes apparently due to being redigitalized from paper, so I can only recommend the former two.
Read some introduction into flows and the Ford-Fulkerson algorithm beforehand.
An alternative way to relate Dilworth's and Mirsky's theorems is by the perfect graph theorem (e. g., done in Schrijver's A Course in Combinatorial Optimization, http://homepages.cwi.nl/~lex/files/dict.pdf ), though I'm not sure if it helps to explain a miracle with an even greater miracle.