Dilworth's Theorem - Width of Special Partial Orders

Width of Special Partial Orders

The Boolean lattice B_n is the power set of an n-element set X—essentially {1, 2, …, n}—ordered by inclusion. Sperner's theorem states that a maximum antichain of B_n has size at most

In other words, a largest family of incomparable subsets of X is obtained by selecting the subsets of X that have median size. The Lubell–Yamamoto–Meshalkin inequality also concerns antichains in a power set and can be used to prove Sperner's theorem.

If we order the integers in the interval by divisibility, the subinterval forms an antichain with cardinality n. A partition of this partial order into n chains is easy to achieve: for each odd integer m in, form a chain of the numbers of the form m2i. Therefore, by Dilworth's theorem, the width of this partial order is n. Abouabdillah's theorem characterizes the integers that can belong to maximum antichains in this order.

The Erdős–Szekeres theorem on monotone subsequences can be interpreted as an application of Dilworth's theorem to partial orders of order dimension two (Steele 1995).

The "convex dimension" of an antimatroid is defined as the minimum number of chains needed to define the antimatroid, and Dilworth's theorem can be used to show that it equals the width of an associated partial order; this connection leads to a polynomial time algorithm for convex dimension (Edelman & Saks 1988).