Hopefully Interesting

March 17, 2008

Dilworth’s Theorem II

Filed under: math.CO,motivated theorems — Pietro @ 6:48 am
Tags: ,

We continue our discussion of Dilworth’s theorem from last time. To recall, we proved by (a very algorithmic) induction that, if (P,\leq ) is a finite poset whose largest antichain has m elements, then P is the union of m chains. Today we’ll see how a batch of standard (and important) techniques can prove the theorem for general P, from the finite case. As before, we will often refer to decompositions of P into chains as colorings of P, which will always be subject to the restriction that two similarly colored elements be comparable. When we wish to emphasize this property, we may employ the term consistent coloring. It is easy to see that colorings using m colors are equivalent to decompositions into m chains.

The standard move for infinite P would be Zorn’s lemma. By going carefully through the second part of our proof, where we “concentrate” each color on top of only one chain, we see that it can be adapted to arbitrary P without too much trouble: instead of looking for the squiggle with the smallest dark red element in its upper monochromatic set, we choose one which has “arbitrarily small” dark red elements there, and put all the dark red on top of it. This gives us the incremental part of a standard argument by Zorn’s Lemma, but our increment potentially involves a lot of fiddling with the chains, so we will probably not be able to define a very demanding order on the set \mathcal{P} of partially-built structures. As we saw, this will probably make it difficult to prove the existence of upper bounds for metachains.

So, let’s scale back the difficulty and consider the case of denumerable P; with countable sets, we can usually build stuff “one element at a time”. Suppose, then, that (P,\leq) is a countable poset without antichains bigger than m. Let a_1,\ldots,a_m be an antichain, and start with a partial decomposition of P into chains \chi_1,\ldots,\chi_m, where \chi_i=\{a_i\} initially. Put P\backslash\{a_1,\ldots,a_m\} = \{p_1,p_2,\ldots,p_n,\ldots\} for definiteness. Using the finite form of Dilworth’s theorem, whereby each finite subset of P can be arranged into m chains, we hope to find such a decomposition of all of P.

Let’s just bulldoze our way forward and see what goes wrong. Stick p_1 in whatever \chi_i it will fit (p_1 must be comparable to at least one a_i, otherwise we’d have an (m+1)-antichain), and continue by putting each p_i in whatever \chi_i is possible. If this can be done indefinitely, we get a decomposition of P. Otherwise, we run into trouble at some p_r, meaning each \chi_i contains, at that point, some x_i not comparable to p_r.

An obvious reaction is to use Dilworth’s: we know that \{p_1,\ldots,p_r\} can in fact be put consistently into the chains \chi_i. We do that, and continue on our merry way.

Unfortunately, it’s not that easy. Decomposing ever larger subsets of P into chains is not enough: we need to harness that information into a single decomposition of P. Let me spell it out in the simple case.

Suppose we don’t run into trouble adding elements of P to the \chi_i, one at a time. How exactly do we specify a decomposition of P from that? That is, given p \in P, to which \chi_i does it belong to? What we had in mind was pretty simple: it belongs to whatever \chi_i it was assigned to, when it was its turn to be added!

Simple as it may be, we must answer a couple of questions. First, is that decomposition well-defined, unambiguous? In this case, yes, since each p\in P is assigned a unique \chi_i in the trouble-free case. Second, is each \chi_i really a chain when all is said and done? Also yes: suppose p_r,p_s\in\chi_i, with r<s. By construction, when p_s was added to \chi_i (at step s), it was comparable to all the elements that had been assigned to \chi_i at that point. In particular, since p_r was added earlier (at step r), p_s must have been comparable to p_r.

Contrast this with the case where we do run into trouble, say at p_r. Invoking Dilworth’s will cause a few among \{p_1,\ldots,p_{r-1}\} to jump around between the \chi_i. If we keep doing this indefinitely, who’s to say that all the p_j eventually settle down and can be assigned a definite \chi_i? And if they don’t, what should we assign them?

Maybe if we take more care in assigning each p_j to a \chi_i, we won’t have to change it afterwards. That is, we won’t have to apply Dilworth again and again. So what should we look out for?

It isn’t very clear how to express the obstructions to avoid in a succint form, e.g. involving only a few kinds of sentence about \leq. Therefore, we resort to another venerable custom of mathematics: just state what you want, flat out, and use the structure arising from that alone.

There are m possible colors for p_1: \chi_1,\ldots,\chi_m. We want to choose the one which runs into the least trouble. Suppose coloring p_1 with \chi_i inevitably runs into trouble at p_{r_i}, in the sense that any extension into a coloring of p_1,\ldots,p_{r_i} has incomparable elements of the same color. A natural choice for the color of p_1 would be that \chi_i with the biggest r_i, ie, that which runs into trouble the latest.

A pleasant fact now asserts itself: there must be a \chi_i without a corresponding r_i! That is, a choice of color for p_1 which admits arbitrarily large extensions. It’s obvious once you think about it: if all colors \chi_1,\ldots,\chi_m ran into dead-ends at p_{r_1},\ldots,p_{r_m}, there would be a largest dead-end r, and we would be unable to color beyond p_r. However, we know that all finite subsets, including \{p_1,\ldots,p_{r+1}\}, admit consistent colorings.

Another way to see it is the following: let (c_1,c_2,c_3\ldots) be the sequence of colors assigned to p_1 in consistent colorings of \{p_1\}, \{p_1,p_2\}, \{p_1,p_2,p_3\} etc. Since there are only m possible colors, at least one must be repeated infinitely many times.

That seems as good a color to give p_1 as any; say it is \chi_1. What next? Well, since there are arbitrarily large colorings with p_1 painted \chi_1, we can run the argument again using only those, and choose a color for p_2 which admits arbitrarily large extensions. And so forth.

To sum up, here’s how we define a coloring of P. For each i, let \mathcal{C}_i be a coloring of \{p_1,\ldots,p_i\}, that is, a map \mathcal{C}_i : \{p_1,\ldots,p_i\} \to \{\chi_1,\ldots,\chi_m\} such that two equally colored elements are comparable. Let c_1 be a color such that arbitrarily large \mathcal{C}_i have \mathcal{C}_i(p_1) = c_1, and let (\mathcal{C}_{1,i})_{i\in\mathbb{N}} be the subsequence of those which do. Inductively, given a subsequence of colorings (\mathcal{C}_{r,i})_{i\in\mathbb{N}}, all of which have the same first r colors, choose a subsequence (\mathcal{C}_{r+1,i})_{i\in\mathbb{N}} whose elements also have the same (r+1)-th color. This is possible because there are only m different colors. Finally, let the “actual” color \mathcal{C}(p_r) of p_r be that assigned by the (\mathcal{C}_{r,i})_{i\in\mathbb{N}}.

This process assigns each p_i a definite color, and the result is consistent. Indeed, if r<s, then \mathcal{C}_{s,1} extends \mathcal{C}_{r,1} (being, in fact, \mathcal{C}_{r,t} for some t); thus, if p_r and p_s are assigned the same color by \mathcal{C}, they are assigned the same color by \mathcal{C}_{s,1}, which, being a consistent coloring, makes p_r and p_s comparable.

So that’s it for countable P. For general P, much the same idea works, with the caveat that we recast the argument in the language of ordinals (for the “step-by-step” angle) or nets in topological spaces (for the “subsequences” angle). We briefly work out the second approach. Let \mathcal{F} be the set of finite subsets of P, and give it the structure of a directed set via \subseteq; an upper bound for two elements is just their set-theoretic union. Give \{1,\ldots,m\}^P the product topology (over the discrete topology in \{1,\ldots,m\}) and define a net x : \mathcal{F} \to \{1,\ldots,m\}^P by setting x_F equal to a consistent coloring of F (given by finite Dilworth) plus some random coloring of P\backslash F. Since \{1,\ldots,m\}^P is compact by Tychonoff’s theorem, there must be a convergent subnet x_{F(\lambda)}\to x_0. It is straightforward to check that x_0 is a consistent coloring of all of P.

There is some crucial finiteness phenomenon underlying the results and arguments above, and it is more clearly seen in the contrapositive form of Dilworth’s theorem: if a poset cannot be decomposed into m chains, then it must contain an antichain of size at least m+1. Therefore, to demonstrate the impossibility of such a decomposition, it suffices to pick out a finite witness: a large, but finite, antichain of P. Such a witness may be expressed by a finite number of statements of the form x \nleq y.

These considerations suggest another approach to the infinite form of Dilworth’s theorem: mathematical logic. In particular, the compactness theorem for first-order logic.

Let \mathcal{L} be a language consisting of the usual symbols for variables, logical connectives and quantifiers, plus a family of constants \{c_p : p\in P\}, a binary relation symbol \preceq and a unary function symbol f. We can encode all the information about (P,\leq) in an \mathcal{L}-theory T_P consisting of the poset axioms plus the sentences:

  • c_a \preceq c_b , for each a,b\in P such that a\leq b;
  • \lnot(c_a\preceq c_b), for each a,b\in P such that a\leq b is not the case;
  • \forall x (f(x)=c_{a_1} \lor \ldots \lor f(x) = c_{a_m});
  • \forall x \forall y (f(x) = f(y) \to (x\preceq y \lor y \preceq x));

Suppose T_P has a model (M,\preceq^M,f^M) with constants c_p^M. We claim that the map p \mapsto c_p^M is an order-theoretic embedding of P in M.

First, all the c_p are distinct: if p\neq q, then one of p\leq q, q \leq p fails to be the case (by antisymmetry), whence either \lnot(c_p \preceq c_q) or \lnot(c_q \preceq c_p) is in T_P. It follows that either c_p^M \preceq^M c_q^M or c_q^M \preceq^M c_p^M fails; and since M is the model of a poset, c_p^M = c_q^M would imply both.

Next, the first two types of sentence of T_P obviously imply that P is order-isomorphic to its image by the map p \mapsto c_p^M. Therefore, if it is possible to decompose M into the union of m chains, the same goes for P. But that’s just what the last two types of sentence of T_P say, with the aid of the function symbol f: its realization f^M splits up P into m subsets (one for each a_i), and each subset is a chain.

To summarize: if T_P has a model M, it can be decomposed into m chains, and has P as a subposet; thus P can be decomposed into m chains.

On the other hand, if T_P didn’t have a model, by the compactness theorem in first-order logic there would be some finite subtheory T_P^0 of T_P that didn’t have a model. However, a finite subtheory, having only a finite number of sentences, can only mention a finite number of the constants c_p; and the finite subposet of P corresponding to those constants, endowed with a decomposition into m chains (finite Dilworth), is a model for that subtheory. Therefore, T_P does have a model, and P is decomposable, as we wished.

Next time, we’ll look at some applications of Dilworth’s theorem in combinatorics, and its relationship to various other famous theorems in that field.


Leave a Comment »

No comments yet.

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

Create a free website or blog at WordPress.com.

%d bloggers like this: