# dual of Dilworth’s theorem

###### Theorem 1.

Let $P$ be a poset of height $h$. Then $P$ can be partitioned into $h$ antichains and furthermore at least $h$ antichains are required.

###### Proof.

Induction on $h$. If $h=1$, then no elements of $P$ are comparable, so $P$ is an antichain. Now suppose that $P$ has height $h\geq 2$ and that the theorem is true for $h-1$. Let $A_{1}$ be the set of maximal elements of $P$. Then $A_{1}$ is an antichain in $P$ and $P-A_{1}$ has height $h-1$ since we have removed precisely one element from every chain. Hence, $P-A_{1}$ can be paritioned into $h-1$ antichains $A_{2},A_{3},\dots A_{h}$. Now we have the partition $A_{1}\cup A_{2}\cup\dots\cup A_{h}$ of $P$ into $h$ antichains as desired.

The necessity of $h$ antichains is trivial by the pigeonhole principle; since $P$ has height $h$, it has a chain of length $h$, and each element of this chain must be placed in a different antichain of our partition. ∎

Title dual of Dilworth’s theorem DualOfDilworthsTheorem 2013-03-22 15:01:49 2013-03-22 15:01:49 justice (4961) justice (4961) 7 justice (4961) Theorem msc 06A06 DilworthsTheorem