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. (more…)

## March 17, 2008

### Dilworth’s Theorem II

Advertisements

## March 6, 2008

### 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.