Dilworth’s Theorem II

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 antichain has elements, then is the union of chains. Today we’ll see how a batch of standard (and important) techniques can prove the theorem for general , from the finite case. As before, we will often refer to decompositions of into chains as colorings of , 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 colors are equivalent to decompositions into chains.

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.