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 on Posets states that if $P$ is a poset and $w(P)$ is the maximum cardinality of antichains in $P$ then there exist a decomposition of P of size $w(P)$.

The question is, why this theorem is not trivial?

Consider that there is a whole paper on Annals of Mathematics devoted to it: Dilworth, Robert P. (1950), "A Decomposition Theorem for Partially Ordered Sets", Annals of Mathematics 51 (1): 161–166, doi:10.2307/1969503.

Best

f

share|improve this question
2  
If that were Dilworth’s theorem, it would be trivial, but in fact Dilworth’s theorem says that the maximum size of an antichain in $P$ equals the minimum size of a partition of $P$ into chains. It’s that last requirement that makes the result non-trivial. –  Brian M. Scott Sep 14 '11 at 9:53
    
@Brian, perhaps you'd like to make that comment an answer. –  Gerry Myerson Sep 14 '11 at 13:33

1 Answer 1

If Dilworth’s theorem just said that every poset $P$ has a decomposition of size $w(P)$, where $w(P)$ is the maximum size of an antichain in $P$, it would indeed be trivial, but Dilworth’s theorem is actually a much stronger statement. It says that if $w(P)$ is finite, then $w(P)$ is equal to the minimum size of any partition of $P$ into chains. The requirement that each member of the partition be a chain is what makes the theorem non-trivial. It isn’t enormously difficult $-$ there are nice short proofs by H. Tverberg (On Dilworth’s decomposition theorem for partially ordered sets, J. Combinatorial Theory 3 (1967), 305-306) and Fred Galvin (A proof of Dilworth’s chain decomposition theorem, Amer. Math. Monthly 101 (1994), 352-353) $-$ but it’s definitely not trivial.

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.