Dilworth’s Theorem II « Hopefully Interesting

March 17, 2008

Dilworth’s Theorem II

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

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.

No Comments Yet »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Hopefully Interesting

March 17, 2008

Dilworth’s Theorem II

No Comments Yet »

Leave a comment

Blogroll