Dilworth's Theorem is a result about the width of partially ordered sets. It is equivalent to (and hence can be used to prove) several beautiful theorems in combinatorics, including Hall's marriage theorem. One well-known corollary of Dilworth's theorem is a result of Erdős and Szekeres on sequences of real numbers: every sequence of rs+1 real numbers has an increasing subsequence of length r+1 or a decreasing subsequence of length s+1.
A partially ordered set is a set with a relation on satisfying:
(1) for all (reflexivity)
(2) if and , then (antisymmetry)
(3) if and , then (transitivity)
Note that for two given elements and , it may not be the case that and are comparable, that is, or . If this is true for all pairs and in , we say that is totally ordered.
The set of people in the world, with defined by "is a direct descendant of," is a partially ordered set. The set of positive integers, with defined by "divides," is a partially ordered set.
Note that neither of these sets are totally ordered. A brother and sister are not comparable in , since they are not direct descendants of each other; and and are not comparable in , since neither divides the other.
There are two natural ways to define the width of a finite partially ordered set, which can be thought of as measuring how far away from totally ordered it is; the width is defined to be a certain positive integer, which is if and only if the set is totally ordered.
A chain in a partially ordered set is a subset of elements which are all comparable to each other. An antichain is a subset of elements, no two of which are comparable to each other.
(Definition 1) The width of a finite partially ordered set is the minimum number of chains needed to cover , i.e. the minimum number of chains such that any element of is in at least one of the chains.
(Definition 2) The width of a finite partially ordered set is the maximum size of an antichain in .
As mentioned above, both of these definitions indicate in some sense how far away is from being totally ordered. Note that a chain is a totally ordered subset of , so both definitions give width for a totally ordered set.
Let be the set of divisors of , with divisibility as the partial order. Then the following chains cover : And is an antichain of length . It is not immediately obvious, but the chain cover is minimal (though not unique), and the antichain is maximal (though not unique). So both definitions of width give for this partially ordered set.
Partially ordered sets are often visualized via Hasse diagrams, which are arrangements of the elements of the set with edges connecting any two comparable elements that have no elements in between them, that is: and are connected if and there is no element such that . The diagram puts above in this case.
Here are two typical examples.
Note that chains are represented in the diagram as series of points linked pairwise by edges. The widths of these sets are and , respectively, using either definition, which corresponds to the "width" of the diagram. Note also that these particular diagrams are drawn so that reading horizontally on any given level produces an antichain. The diagram also helps clarify the fact we cited earlier, that the size of an antichain is at least as large as the number of chains required to cover the set.
So Dilworth's Theorem says that the two definitions of width given above coincide with each other.
Dilworth's Theorem: Let be a finite partially ordered set. The size of a maximal antichain equals the size of a minimal chain cover of .
As is often the case, when proving that two quantities are equal, the proof shows that they are less than or equal to each other. One of these inequalities is much easier than the other: Suppose the maximal antichain has length ; then any chain cover has to have at least chains, because no two members of the antichain can be in the same chain, but they each have to be in one of the chains because the chains cover.
The other half of the proof of the theorem is given at the end of this wiki. The following "dual" theorem is easier to prove:
Mirsky's Theorem: Let be a finite partially ordered set. The size of a maximal chain in equals the size of a minimal antichain cover of .
Proof of Mirsky's Theorem: Again, one half is easy. Suppose the maximal chain has length ; then any antichain cover has at least antichains, since no two elements of the chain can be in the same antichain.
Now define a function by the size of a maximal chain whose largest element is . Note that if , then and cannot be comparable (why?). So, for any positive integer , the set of all the elements such that is an antichain. If the maximal chain has length , then the sets form an antichain cover of . It is not immediately obvious that these sets are all nonempty (though they are), but this shows that there is an antichain cover of size at most , which is the second half of the proof of the theorem.
One way to view the sets constructed in the proof are as the horizontal "strips" of the Hasse diagram, if it is drawn in such a way that a point is put on level if the longest chain ending in that point has length . It is straightforward to check that the two Hasse diagrams in the above examples are constructed in that way.
Erdős-Szekeres Theorem: A sequence of at least real numbers has an increasing subsequence of length or a decreasing subsequence of length .
For instance: any sequence of real numbers has an increasing subsequence of length or a decreasing subsequence of length . Or: any sequence of real numbers has a monotone subsequence of length .
Proof: Suppose we are given a sequence of real numbers. Define an ordering on this sequence by if and . A chain with respect to this ordering is just an increasing subsequence, and an antichain is a decreasing subsequence. Suppose there is no antichain of length . Then the width of the set is at most , so by Dilworth's Theorem the set can be covered by chains. If all of these chains have length , then the set has at most elements, which is impossible. So at least one of the chains has length , so there is an increasing subsequence of length .
This is a special case of a general fact about partially ordered sets, which follows from Dilworth's Theorem in exactly the same way:
A partially ordered set of size has a chain of length or an antichain of length .
Let be intervals on the real number line. Suppose that no four of the intervals are disjoint. Show that there must be four intervals that share a common point.
Solution: Define a partial order by if and only if and are disjoint and is to the left of . The assumption is that there is no chain of length , so there must be an antichain of length , which is a subset of four intervals, no two of which are disjoint. Hence they share a common point. (Why?)
The easiest proof is by induction on the size of the set. Let be the size of the largest antichain of . The proof will show that can be covered by chains. The base case is trivial. So suppose the result has been proven for all sets smaller than .
First, if no two elements of are comparable, then itself is an antichain and it can be covered by chains each of length , so the result holds. Otherwise, consider the set of elements of which are comparable to at least one other element of Let be a minimal element of this set ( for all comparable ), and choose to be a maximal element of the nonempty subset Then is clearly a maximal element ( for all comparable ). Let . If the largest antichain in has size , then can be covered by chains, and so can be covered by those plus the chain , and the result will be proven for .
So now suppose that the largest antichain in has size (it can't be larger because is a subset of ). Call this antichain .
The idea of the rest of the proof is: picture the Hasse diagram for where the largest antichain consists of a horizontal strip. Take everything below the strip and everything above the strip, use induction to cover these by chains, and then link the chains together by connecting them across the strip.
That is, construct the two sets Then must be all of , because if it weren't then would not be a maximal antichain in . And , because if is in the intersection, then for some elements , so and are comparable by transitivity, so the only possibility is that and they both equal .
Since and are not in , it must be the case that and , so both sets and are strictly smaller than . The inductive hypothesis applies to both and , so they are both covered by chains, each of which must contain exactly one element of . Call them and . Now we can stitch together these covers to get a cover of all of , by the chains . This cover has chains, so the result follows by induction.