## You are here

Homedual of Dilworth's theorem

## Primary tabs

# 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. ∎

## Mathematics Subject Classification

06A06*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff

## Recent Activity

new question: Harshad Number by pspss

Sep 14

new problem: Geometry by parag

Aug 24

new question: Scheduling Algorithm by ncovella

new question: Scheduling Algorithm by ncovella