Dilworth's theorem

From Wikipedia, the free encyclopedia

In mathematics, in the area of order theory, Dilworth's theorem characterizes the width of any partially ordered set in terms of a partition of the order into a minimum number of chains. It is named for the mathematician Robert P. Dilworth.

An antichain in a partially ordered set is a set of elements no two of which are comparable to each other, and a chain is a set of elements every two of which are comparable. Dilworth's theorem states that there exists an antichain A, and a partition of the order into a family P of chains, such that the number of chains in the partition equals the cardinality of A. When this occurs, A must be the largest antichain in the order, for any antichain can have at most one element from each member of P. Similarly, P must be the smallest family of chains into which the order can be partitioned, for any partition into chains must have at least one chain per element of A. The width of the partial order is defined as the common size of A and P.

1 Proof via König's theorem
2 Dual of Dilworth's theorem
3 Perfection of comparability graphs
4 Width of special partial orders
5 References
6 External links

[edit] Proof via König's theorem

Proof of Dilworth's theorem via König's theorem: constructing a bipartite graph from a partial order, and partitioning into chains according to a matching

Like a number of other results in combinatorics, Dilworth's theorem is equivalent to König's theorem on bipartite graph matching and several other related theorems including Hall's Marriage theorem.

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). Let P be a family of chains formed by including x and y in the same chain whenever there is an edge (x,y) in M; then P has n - m chains. Therefore, we have constructed an antichain and a partition into chains with the same cardinality.

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 an edge 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.

[edit] Dual of Dilworth'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: find for each element x the largest chain in which x is the largest element. The subsets of the elements that have equal sized chains form the desired partition into antichains.

[edit] Perfection 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 the dual of Dilworth's theorem, restated in graph-theoretic terms. It is known that 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.

[edit] Width of special partial orders

The power set P[X] of a finite set X of size n may be ordered by inclusion. Sperner's theorem states that a maximum antichain has size at most

$\mbox{width}(P[X]) = {n \choose \lfloor{n/2}\rfloor}.$

In other words, the largest family of incomparable subsets of X can be found 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 m2ⁱ. 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.

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.