Of all the results in lattice theory, perhaps the most famous is Dilworth's Theorem for decomposition of a poset. Dilworth's Theorem belongs to the special class of results, called min–max results, which relate a maximal value in a structure to a minimal value. Dilworth's Theorem states that the minimum number of chains a poset can be partitioned into equals the maximum size of an antichain. In this chapter, we cover this result and associated algorithms.
3.2 Dilworth's Theorem
We first present a proof of Dilworth's Theorem due to Galvin [Gal94].