- #1
Wildcat
- 116
- 0
Homework Statement
If in a poset all chains have at most 10 elements, prove that the poset can be partitioned into k anti-chains for some k≤10.
Homework Equations
The Attempt at a Solution
Let X be the poset whose chains have at most 10 elements. Let C be a maximum length chain (10 elements) in X. Let N be the set of maximal elements of X. N is an anti-chain in X. Use induction on k. If k=1, the maximal element of a chain then the poset contains 1 anti-chain. So it holds true for k=1. For the poset X – N, the length of the largest chain would be k – 1. This implies that X can be partitioned into k-1 anti-chains. So by induction, X can be partitioned into k≤10 anti-chains. What am I missing?
Last edited: