3
$\begingroup$

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

  • 0
    @Brian, perhaps you'd like to make that comment an answer.2011-09-14

1 Answers 1

11

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.