Dilworth's theorem

In mathematics, in the areas of order theory and combinatorics, Dilworth's theorem states that, in any finite partially ordered set, the maximum size of an antichain of incomparable elements equals the minimum number of chains needed to cover all elements.

The theorem is named for the mathematician Robert P. Dilworth, who published it in 1950.

[1] A version of the theorem for infinite partially ordered sets states that, when there exists a decomposition into finitely many chains, or when there exists a finite upper bound on the size of an antichain, the sizes of the largest antichain and of the smallest chain decomposition are again equal.

Dilworth's theorem states that, in any finite partially ordered set, the largest antichain has the same size as the smallest chain decomposition.

The width of the partial order is defined as the common size of the antichain and chain decomposition.

The following proof by induction on the size of the partially ordered set

[2] To prove Dilworth's theorem for a partial order S with n elements, using Kőnig's theorem, define a bipartite graph G = (U,V,E) where U = V = S and where (u,v) is an edge in G when u < v in S. By Kőnig's theorem, there exists a matching M in G, and a set of vertices C in G, such that each edge in the graph contains at least one vertex in C and such that M and C have the same cardinality m. Let A be the set of elements of S that do not correspond to any vertex in C; then A has at least n - m elements (possibly more if C contains vertices corresponding to the same element on both sides of the bipartition) and no two elements of A are comparable to each other.

To prove Kőnig's theorem from Dilworth's theorem, for a bipartite graph G = (U,V,E), form a partial order on the vertices of G in which u < v exactly when u is in U, v is in V, and there exists an edge in E from u to v. By Dilworth's theorem, there exists an antichain A and a partition into chains P both of which have the same size.

But the only nontrivial chains in the partial order are pairs of elements corresponding to the edges in the graph, so the nontrivial chains in P form a matching in the graph.

The complement of A forms a vertex cover in G with the same cardinality as this matching.

This connection to bipartite matching allows the width of any partial order to be computed in polynomial time.

More precisely, n-element partial orders of width k can be recognized in time O(kn2).

[3] 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.

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.

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.

[4] Perles (1963) discusses analogues of Dilworth's theorem in the infinite setting.

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.

Its proof 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.

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.

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.

Therefore, the complement of any comparability graph is perfect; this is essentially just Dilworth's theorem itself, restated in graph-theoretic terms (Berge & Chvátal 1984).

Thus, the complementation property of perfect graphs can provide an alternative proof of Dilworth's theorem.

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.

[7] 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.