Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
If I recall correct Dilworth's theorem states this only for finite posets, or maybe posets with a finite width. –  Asaf Karagila Jan 29 '13 at 16:44
    
I'm interested in finite partial orders, I edited the question to reflect this. Thanks for this remark! –  a3nm Jan 29 '13 at 16:45

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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