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 14, 2008

Quantitative Borel-Cantelli Lemma

Filed under: math.CA,motivated theorems — Pietro @ 12:00 pm
Tags: ,

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 (X,\mathcal{M},\mu) be a measure space, and (E_n)_{n\in\mathbb{N}} a sequence of measurable sets such that \sum_{n\in\mathbb{N}} \mu(E_n) < \infty. Then the points of X that lie in infinitely many E_n 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 F_\infty to be the set of points lying in infinitely many E_n, and notice that F_\infty = \bigcap_{n\in\mathbb{N}} \bigcup_{k\geq n} E_k. It follows that F_\infty is measurable, and contained in each cofinite union \bigcup_{k\geq n} E_k. Now, \mu(\bigcup_{k\geq n}E_k) \leq \sum_{k\geq n} \mu(E_k), and the latter goes to zero as n\to\infty, because \sum_{n\in\mathbb{N}} \mu(E_n) converges. Thus \mu(F_\infty)=0, as claimed. \Box

Alright, so the set of points lying in “very many” E_n is “very small”. A natural quantitative question to ask at this point is: how small is the set of points lying in “moderately many” E_n? More precisely, if F_k is the set of points lying in at least k of the E_n, and G_k = F_k \backslash F_{k+1} the set of points lying in exactly k of the E_n, can we get bounds on \mu(F_k) and \mu(G_k), depending on k?

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