# On Dilworth's theorem

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

-
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

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.