of comparability graphs A comparability graph is an undirected graph formed from a partial order by creating a vertex per element of the order, and an edge connecting any two comparable elements. Thus, a clique in a comparability graph corresponds to a chain, and an independent set in a comparability graph corresponds to an antichain. Any induced subgraph of a comparability graph is itself a comparability graph, formed from the restriction of the partial order to a subset of its elements. An undirected graph is perfect if, in every induced subgraph, the chromatic number equals the size of the largest clique. Every comparability graph is perfect: this is essentially just Mirsky's theorem, restated in graph-theoretic terms . By the perfect graph theorem of , the complement of any perfect graph is also perfect. Therefore, the complement of any comparability graph is perfect; this is essentially just Dilworth's theorem itself, restated in graph-theoretic terms . Thus, the complementation property of perfect graphs can provide an alternative proof of Dilworth's theorem. Width of special partial orders The Boolean lattice Bn is the power set of an n-element set X—essentially {1, 2, …, n}—ordered by inclusion or, notationally, (2[n], ⊆). Sperner's theorem states that a maximum antichain of Bn 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 [1, 2n] by divisibility, the subinterval [n + 1, 2n] 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 [1,2n], form a chain of the numbers of the form m2i. Therefore, by Dilworth's theorem, the width of this partial order is n. 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 . 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 . References . . . . . . . . . .