info prev up next book cdrom email home

Dilworth's Lemma

The Width of a set $P$ is equal to the minimum number of Chains needed to Cover $P$. Equivalently, if a set $P$ of $ab+1$ elements is Partially Ordered, then $P$ contains a Chain of size $a+1$ or an Antichain of size $b+1$. Letting $N$ be the Cardinality of $P$, $W$ the Width, and $L$ the Length, this last statement says $N\leq LW$. Dilworth's lemma is a generalization of the Erdös-Szekeres Theorem. Ramsey's Theorem generalizes Dilworth's lemma.

See also Combinatorics, Erdös-Szekeres Theorem, Ramsey's Theorem

© 1996-9 Eric W. Weisstein