2008 March « Hopefully Interesting

March 17, 2008

Dilworth’s Theorem II

Filed under: math.CO, motivated theorems — Pietro @ 6:48 am
Tags: combinatorics, logic

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: analysis, combinatorics

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: combinatorics

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.