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
Canonical name	DualOfDilworthsTheorem
Date of creation	2013-03-22 15:01:49
Last modified on	2013-03-22 15:01:49
Owner	justice (4961)
Last modified by	justice (4961)
Numerical id	7
Author	justice (4961)
Entry type	Theorem
Classification	msc 06A06
Related topic	DilworthsTheorem