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

March 6, 2008

Dilworth’s Theorem I

Filed under: math.CO,motivated theorems — Pietro @ 10:46 am
Tags:

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 (P,\leq ) be a partially ordered set (a poset) in which the largest antichain has size m. Then it is possible to decompose P into the union of m chains.

(more…)

Blog at WordPress.com.