Dilworth's lemma

cosmos 15th October 2017 at 9:37pm
Antichain Chain set

Let (P,)(P,\leq) be a finite poset. The minimum number of chains needed to cover PP is equal to the maximum size of an antichain.

This is similar to theorems like Max-flow min-cut theorem. We can see that any partition into chain gives an upper bound on the size of an antichain (think of constructing the antichain element by element, you always have to choose the new element from a new chain in the partition. A chain and an antichain meet in at most one element). Then, the smallest possible partition gives the smallest bound of this type. And one can prove that the bound is tight.

Proof here

There is a ‘dual’ of Dilworth’s Theorem: the minimum number of antichains in a cover P is equal to the maximum size of a chain. The proof of this is an exercise on the first example sheet.

See also Sperner's lemma.