Dilworth's Theorem

Minimum chain cover equals maximum antichain in any finite poset.

The idea

Theorem (Dilworth's theorem).

In a finite partially ordered set, the smallest number of chains that together cover every element equals the largest size of an antichain.

A partial order leaves some pairs uncompared: among the divisors of a number ordered by divisibility, for instance, two divisors may divide neither one another. A chain is a set of elements that are pairwise comparable; an antichain is a set of elements no two of which are comparable. The theorem equates the extremes of these two notions.

One inequality is immediate. Two elements of a chain are always comparable, so a chain contains at most one member of any antichain; if some antichain has $k$ elements, no cover by fewer than $k$ chains reaches all of them. Dilworth's theorem supplies the converse: a cover by exactly $k$ chains exists, where $k$ is the maximum antichain size.

The equality makes the theorem a certificate. Exhibit an antichain of size $k$ and a cover by $k$ chains, and the minimum is pinned at exactly $k$: the theorem guarantees that no smaller cover exists.

Ways to work on it

• Walkthrough. Chains, antichains, and the min-max equality on the divisibility poset.
• Practice. Read off the shared min-max value on a small poset.
• Hardest. Certify the minimum chain cover with a matching antichain.

Not sure where to start? Take the ten-question placement test.