be computed in polynomial time. More precisely, n-element partial orders of width k can be recognized in time O(kn2) . Extension to infinite partially ordered sets Dilworth's theorem for infinite partially ordered sets states that a partially ordered set has finite width w if and only if it may be partitioned into w chains. For, suppose that an infinite partial order P has width w, meaning that there are at most a finite number w of elements in any antichain. For any subset S of P, a decomposition into w chains (if it exists) may be described as a coloring of the incomparability graph of S (a graph that has the elements of S as vertices, with an edge between every two incomparable elements) using w colors; every color class in a proper coloring of the incomparability graph must be a chain. By the assumption that P has width w, and by the finite version of Dilworth's theorem, every finite subset S of P has a w-colorable incomparability graph. Therefore, by the De Bruijn–Erdős theorem, P itself also has a w-colorable incomparability graph, and thus has the desired partition into chains . However, the theorem does not extend so simply to partially ordered sets in which the width, and not just the cardinality of the set, is infinite. In this case the size of the largest antichain and the minimum number of chains needed to cover the partial order may be very different from each other. In particular, for every infinite cardinal number κ there is an infinite partially ordered set of width ℵ0 whose partition into the fewest chains has κ chains . discusses analogues of Dilworth's theorem in the infinite setting. Dual of Dilworth's theorem (Mirsky's theorem) A dual of Dilworth's theorem states that the size of the largest chain in a partial order (if finite) equals the smallest number of antichains into which the order may be partitioned . The proof of this is much simpler than the proof of Dilworth's theorem itself: for any element x, consider the chains that have x as their largest element, and let N(x) denote the size of the largest of these x-maximal chains. Then each set N−1(i), consisting of elements that have equal values of N, is an antichain, and these antichains partition the partial order into a number of antichains equal to the size of the largest chain. Perfection