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

## March 14, 2008

### Quantitative Borel-Cantelli Lemma

Everyone knows and loves the Borel-Cantelli lemma: it is widely used, intuitive and has a cute proof. Let’s recall it.

**Borel-Cantelli Lemma.** Let be a measure space, and a sequence of measurable sets such that . Then the points of that lie in infinitely many form a set of measure zero.

*Proof.* We present the usual slick proof of the lemma, and postpone intuition until the development of a quantitative statement. Define to be the set of points lying in infinitely many , and notice that . It follows that is measurable, and contained in each cofinite union . Now, , and the latter goes to zero as , because converges. Thus , as claimed.

Alright, so the set of points lying in “very many” is “very small”. A natural quantitative question to ask at this point is: how small is the set of points lying in “moderately many” ? More precisely, if is the set of points lying in at least of the , and the set of points lying in exactly of the , can we get bounds on and , depending on ?

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