Dilworth's Theorem
Vijay K. Garg · 2015
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 a 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. This chapter covers this result and associated algorithms. It first presents a proof of Dilworth's Theorem. The chapter provides another proof which is based on removing a chain instead of an element as in Galvin's proof. This is closer to Dilworth's original proof. The relationship between the problem of chain partition of a poset and matching in a bipartite graph is further explained.