Dilworth’s Theorem I

Today I’d like to talk about a gorgeous theorem in order theory. Since partial orders are such general objects, the theorem potentially has many applications, especially in combinatorics (we shall see a few, in fact); and to top it off, I found a very cute inductive proof.

Here’s the statement:

Theorem 1. Let be a partially ordered set (a poset) in which the largest antichain has size . Then it is possible to decompose into the union of chains.

The key terms are chain and antichain; here are quick definitions. We say that two elements are comparable if either or is the case. Recall that, in a partial order, not all pairs of elements are required to be comparable — hence the term, partial.

A chain in is a subset of , where any two elements are comparable. An antichain, on the other hand, is a subset of such that no two elements of are comparable. If we give the divisibility order to the set of natural numbers (whereby iff divides ), then the set is a chain, whereas is an antichain.

Intuitively, the chains of a poset are long “noodles”, like below:

Antichains, on the other hand, are independent sets, and the largest antichain is a sort of “diameter” of the poset. In the above picture each “floor” of the diagram is an antichain, for instance .

If we would like to decompose into a union of chains, it’s obvious we need at least as many chains as there are elements in the largest antichain; any less, and two incomparable elements would have to be in the same chain. Trying out a few cases like the above, it’s plausible to conjecture we don’t need any more:

There are a few routes we may choose in our search of a proof. First, as our initial optimistic conjecture (and the statement of theorem 1) places no restriction on , it may be an infinite set. A very large infinite set. And for building structures on infinite sets there’s nothing like Zorn’s lemma.

A prototype proof along these lines would need

1. a suitable set of “partially-built” structures, e.g. the set of decompositions of subsets of into chains;
2. a notion of ordering for those, which could be a straightforward “extends” relation, e.g. “each chain in one decomposition is contained in a chain of the other decomposition”;
3. an upper bound on each chain of partial structures, e.g. the decomposition into the union of the chains;
4. an incremental argument, which, given a partial structure which does not encompass all of , adds something to it.

To avoid confusion of the senses of “chain” and “order” — as applied to the original poset, and to the set of partially-built structures — I will use the terms metachain and metaorder for the latter.

Getting back on track: there is always a”law of conservation of difficulty” in such situations. If we choose the metaorder in (2) to be very demanding, so that the upper bound in (3) is e.g. a simple union of the elements of the metachain (like the hypothetical (2) would allow), we become severly restricted in our incremental arguments: tweak a partial structure a little, and the result winds up not extending, but being incomparable with the original version. On the other hand, if the metaorder is very permissive, increments become easy, but even elements of the same metachain start to have little in common, and one can’t harness them (as in a simple union) to produce an upper bound.

Let’s go with the idea in (1) and try out different metaorders. To formalize, let be a maximum antichain in , and define

is a chain in and .

Our hope is that contains some element whose chains cover .

We define two orders on :

iff, for each , ;

iff .

Obviously, is a lot more demanding than . In particular, the easy union argument applies to the former: if is a metachain under , then is an upper bound for it. On the other hand, given a tuple of chains, whose union doesn’t cover , it’s hard to see how to extend it.

Suppose doesn’t belong to any , and can’t be straighforwardly inserted into one — say there’s at least one element in each that isn’t comparable with . Then we’re pretty much lost: if we remove elements from any , to make way for the new , the resulting tuple of chains will fail to be metacomparable with the original one.

To avoid “bad choices” leading up to such a dead-end, we could restrict the set to “good partial choices” in some way — but how? Let’s save this approach for later and try something else.

For the easygoing metaorder , it looks as if we could more easily increment : as long as we add a new element to some , and just move elements around between them, without removing any, we’re guaranteed to get a larger partial structure. Even if we make some “bad choices” along the way, we may be able to cleverly rearrange the elements among the and manage to fit the new guy in. However, a metachain in can contain very diverse elements, and the straightforward union idea will likely break the chain property of each , so it’s unclear how to get upper bounds on general metachains.

There is one case where our inability to get upper bounds is not a problem: when is a finite set. Then we can just run the incremental part of the argument a bunch of times and prove the theorem. Besides, proving it first for finite would be taking Pólya’s advice: “if there’s a problem you can’t solve, there is an easier problem you can solve.”

One other piece of insight that might prod us in this direction is the observation that partial orders can be incredibly intricate: many non-trivial structures, from a lattice of subgroups to the state space of a distributed system, can be represented by a partial order. Therefore, we may expect the construction of an explicit decomposition of a partial order into chains to be very algorithmic in nature, that is, to proceed by building and changing partial structures that cannot be described simply (in the Kolmogorov complexity sense, for instance).

So let’s jump right in. Let be our finite poset, one of its maximum antichains, and suppose we have a tuple of chains , where , whose union is not quite all of . Let belong to none of the chains. If there is a such that is comparable to all of its elements, we just stick in there and move on. Otherwise, in each there are elements not comparable to .

And they have usable structure, too. In each , among the elements not comparable to , there is a greatest, , and a least, , because is a chain. Moreover, no element between and is comparable to , otherwise transitivity would give a contradiction. We present the situation schematically below. Each color (red, green, blue) represents a chain, and dots further down are dots further up. Dark hues are elements not comparable to .

Now, notice that any dark antichain (composed only of dark elements) can be extended by adding in . Since our poset has no antichains bigger than , it follows that there are no dark antichains with more than elements. If this doesn’t scream inductive hypothesis, I don’t know what does.

Heeding the screams, we decompose the subposet of dark elements into chains, say , which we picture as black squiggles:

Notice that this breaks each into an upper and a lower half, which we denote and , respectively. (Either, or both, may be empty.)

We want to somehow rearrange this mess into tidy chains. Recall that, by construction, is comparable to all the brightly-colored elements, being less than the ones above it, and greater than the ones below. This means we can stick in a chain in many different ways; just choose any , any , and connect them by :

The next step is almost too obvious to be wrong. Here we have “upper halves” of chains, “lower halves”, and precisely candidates for connecting stuff: itself, and the dark chains. We just have to prove the ends can be tied up properly.

But we run into a little trouble. Choose one of the at random; where can we tie its top and bottom ends? Offhand, the most obvious thing to do is match colors: tie the top end to the which is the same color as ’s greatest element, and similarly for the bottom end. By construction, we’re guaranteed to wind up with a chain:

But what happens if the top ends of the squiggles repeat colors? That is, what if two or more dark chains have largest elements of the same color? Then we can’t do the obvious tie-ups, and there don’t seem to be any clever tie-ups, either. This is where the proof becomes “algorithmic” for the second time (the first was the recursive bit, at the inductive hypothesis).

The main observation is that we can “concentrate” all the similarly-colored top ends in just one place — wherever the top end is smallest. Indeed, suppose and have “dark red” (say, ) tops, and consider the longest run of consecutive elements in each, starting from the top. That is, we look not only at the top element of , but see how far down the dark red goes, before some other color appears. Call these “monochromatic top sets” and , respectively. Since they are finite and the same color, is a chain and has a least element, say . Now just move all of to whichever of , contained in the first place. Say it was . Since was in the monochromatic top set, it is larger than all non- elements in ; and since it was the least element, everything we added to is also larger than the non- stuff. In other words, is still a chain. As they say, a picture is worth a thousand words:

We may iterate this procedure until all the “dark red” is sitting on top of a single squiggle (dark chain). Then we do it for the other colors, and also for the bottom ends. In the end, each color will sit on top of at most one squiggle, and lay at the bottom of at most one squiggle. This allows us to perform the obvious tie-ups discussed earlier, and still have upper and lower half-chains left over. Finally, we connect one of each through (remember him?), and tie up any remaining halves directly. Voilà! We managed to stick one more element in an -chain decomposition of , and the inductive step is complete.

So we’ve managed to prove Theorem 1 for finite . In the following post, we’ll see how the infinite case drops out easily, and discuss the relationship of Dilworth’s theorem with other famous theorems from combinatorics.