You are here
Home ›dual of Dilworth's theorem
Primary tabs
dual of Dilworth’s theorem
Theorem 1.
Let be a poset of height . Then can be partitioned into antichains and furthermore at least antichains are required.
Proof.
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.
The necessity of antichains is trivial by the pigeonhole principle; since has height , it has a chain of length , and each element of this chain must be placed in a different antichain of our partition. ∎
Related:
DilworthsTheorem
Type of Math Object:
Theorem
Major Section:
Reference
Mathematics Subject Classification
06A06 Partial order, general- 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
May 20
new question: Taylor's Series Query! by Bruce Lee
new question: Laplace transform by J
new question: Residue Calculus by J
May 19
new Education: Project: PlanetMath Outlines Series by unlord
May 17
new image: sinx_approx.png by jeremyboden
new image: approximation_to_sinx by jeremyboden
new image: approximation_to_sinx by jeremyboden
new question: Solving the word problem for isomorphic groups by unlord
new image: LineDiagrams.jpg by m759
new image: ProjPoints.jpg by m759
new question: Taylor's Series Query! by Bruce Lee
new question: Laplace transform by J
new question: Residue Calculus by J
May 19
new Education: Project: PlanetMath Outlines Series by unlord
May 17
new image: sinx_approx.png by jeremyboden
new image: approximation_to_sinx by jeremyboden
new image: approximation_to_sinx by jeremyboden
new question: Solving the word problem for isomorphic groups by unlord
new image: LineDiagrams.jpg by m759
new image: ProjPoints.jpg by m759


