dual of Dilworth’s theorem

Theorem 1.

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


InductionMathworldPlanetmath on h. If h=1, then no elements of P are comparablePlanetmathPlanetmath, so P is an antichain. Now suppose that P has height h2 and that the theorem is true for h-1. Let A1 be the set of maximal elementsMathworldPlanetmath of P. Then A1 is an antichain in P and P-A1 has height h-1 since we have removed precisely one element from every chain. Hence, P-A1 can be paritioned into h-1 antichains A2,A3,Ah. Now we have the partitionMathworldPlanetmathPlanetmath A1A2Ah of P into h antichains as desired.

The necessity of h antichains is trivial by the pigeonhole principleMathworldPlanetmath; 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