dual of Dilworth’s theorem
Let be a poset of height . Then can be partitioned into antichains and furthermore at least antichains are required.
Induction on . If , then no elements of are comparable, so is an antichain. Now suppose that has height and that the theorem is true for . Let be the set of maximal elements of . Then is an antichain in and has height since we have removed precisely one element from every chain. Hence, can be paritioned into antichains . Now we have the partition of into antichains as desired.
|Title||dual of Dilworth’s theorem|
|Date of creation||2013-03-22 15:01:49|
|Last modified on||2013-03-22 15:01:49|
|Last modified by||justice (4961)|