Hopefully Interesting

March 6, 2008

Dilworth’s Theorem I

Filed under: math.CO,motivated theorems — Pietro @ 10:46 am

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 (P,\leq ) be a partially ordered set (a poset) in which the largest antichain has size m. Then it is possible to decompose P into the union of m chains.

The key terms are chain and antichain; here are quick definitions. We say that two elements x,y \in P are comparable if either x \leq y or y \leq x 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 P is a subset C of P, where any two elements are comparable. An antichain, on the other hand, is a subset A of P such that no two elements of A are comparable. If we give the divisibility order to the set of natural numbers (whereby x \leq y iff x divides y), then the set \{1,2,4,8\} is a chain, whereas \{2,3,5,7\} is an antichain.

Intuitively, the chains of a poset are long “noodles”, like \emptyset \subset \{x\} \subset \{x,y\} \subset \{x,y,z\} below:

Example of partial order

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 \{ \ \{x\}, \{y\}, \{z\} \ \}.

If we would like to decompose P 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:

Decomposition of poset into chains

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 P, 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 P 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 P, 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 \{a_1,\ldots,a_m\} be a maximum antichain in P, and define

\mathcal{P} = \{ (\chi_1, \ldots , \chi_m) \ : \ \chi_i is a chain in P and a_i \in \chi_i \}.

Our hope is that \mathcal{P} contains some element whose chains cover P.

We define two orders on \mathcal{P}:

(\chi_1, \ldots , \chi_m) \leq (\chi_1', \ldots , \chi_m') iff, for each i, \chi_i \subseteq \chi_i';

(\chi_1, \ldots , \chi_m) \preceq (\chi_1', \ldots , \chi_m') iff \bigcup_i \chi_i \subseteq \bigcup_i \chi_i'.

Obviously, \leq is a lot more demanding than \preceq. In particular, the easy union argument applies to the former: if (\chi_i^{(j)},\ldots,\chi_m^{(j)})_{j\in J} is a metachain under \leq, then (\cup_j \chi_i^{(j)},\ldots,\cup_j \chi_m^{(j)}) is an upper bound for it. On the other hand, given a tuple (\chi_1, \ldots , \chi_m) of m chains, whose union doesn’t cover P, it’s hard to see how to extend it.

Suppose x \in P doesn’t belong to any \chi_i, and can’t be straighforwardly inserted into one — say there’s at least one element in each \chi_i that isn’t comparable with x. Then we’re pretty much lost: if we remove elements from any \chi_i, to make way for the new x, 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 \mathcal{P} to “good partial choices” in some way — but how? Let’s save this approach for later and try something else.

For the easygoing metaorder \preceq, it looks as if we could more easily increment (\chi_1, \ldots , \chi_m): as long as we add a new element to some \chi_i, 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 \chi_i and manage to fit the new guy in. However, a metachain in \preceq can contain very diverse elements, and the straightforward union idea will likely break the chain property of each \chi_i, 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 P 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 P 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 (P,\leq ) be our finite poset, \{a_1,\ldots,a_m\} one of its maximum antichains, and suppose we have a tuple of chains (\chi_1,\ldots,\chi_m), where a_i \in \chi_i, whose union is not quite all of P. Let x \in P belong to none of the chains. If there is a \chi_i such that x is comparable to all of its elements, we just stick x in there and move on. Otherwise, in each \chi_i there are elements not comparable to x.

And they have usable structure, too. In each \chi_i, among the elements not comparable to x, there is a greatest, M, and a least, m, because \chi_i is a chain. Moreover, no element between m and M is comparable to x, 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 \leq dots further up. Dark hues are elements not comparable to x.

Dark elements not comparable to x

Now, notice that any dark antichain (composed only of dark elements) can be extended by adding in x. Since our poset P has no antichains bigger than m, it follows that there are no dark antichains with more than m-1 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 m-1 chains, say \Delta_1,\ldots,\Delta_{m-1}, which we picture as black squiggles:

Got m-1 dark chains by inductive hypothesis

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

We want to somehow rearrange this mess into m tidy chains. Recall that, by construction, x 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 x in a chain in many different ways; just choose any \chi_i^+, any \chi_j^-, and connect them by x:

Sticking the ends together

The next step is almost too obvious to be wrong. Here we have m “upper halves” of chains, m “lower halves”, and precisely m candidates for connecting stuff: x itself, and the m-1 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 \Delta_i 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 \chi_j^+ which is the same color as \Delta_i‘s greatest element, and similarly for the bottom end. By construction, we’re guaranteed to wind up with a chain:

The obvious way to tie ends up

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 \Delta_i and \Delta_j have “dark red” (say, \chi_1) tops, and consider the longest run of consecutive \chi_1 elements in each, starting from the top. That is, we look not only at the top element of \Delta_i,\Delta_j, but see how far down the dark red goes, before some other color appears. Call these “monochromatic top sets” A and B, respectively. Since they are finite and the same color, A \cup B is a chain and has a least element, say \varepsilon. Now just move all of A\cup B to whichever of \Delta_i, \Delta_j contained \varepsilon in the first place. Say it was \Delta_j. Since \varepsilon was in the monochromatic top set, it is larger than all non-\chi_1 elements in \Delta_j; and since it was the least \chi_1 element, everything we added to \Delta_j is also larger than the non-\chi_1 stuff. In other words, \Delta_j is still a chain. As they say, a picture is worth a thousand words:

Rearranging elements in the dark chains

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 m-1 obvious tie-ups discussed earlier, and still have upper and lower half-chains left over. Finally, we connect one of each through x (remember him?), and tie up any remaining halves directly. Voilà! We managed to stick one more element in an m-chain decomposition of P, and the inductive step is complete.

So we’ve managed to prove Theorem 1 for finite P. 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.


1 Comment »

  1. […] theorems — Pietro @ 6:48 am We continue our discussion of Dilworth’s theorem from last time. To recall, we proved by (a very algorithmic) induction that, if is a finite poset whose largest […]

    Pingback by Dilworth’s Theorem II « Hopefully Interesting — March 17, 2008 @ 6:48 am | Reply

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

Blog at WordPress.com.

%d bloggers like this: