Dilworth's theorem

Remarks

The easy half: a chain meets an antichain in at most one element, so any cover of $P$ by chains uses at least $w$ chains. The hard half can be proved by induction on $\abs{P}$, by removing a maximal chain or by splitting $P$ along a maximum antichain. Another proof builds a bipartite graph with two copies of $P$ and an edge from $x$ to $y$ when $x < y$; then Kőnig's theorem on matchings gives the chain partition. Example: in the set $\set{1, 2, \ldots, 10}$ ordered by divisibility, the set $\set{6, 7, 8, 9, 10}$ is an antichain of size $5$, and $\set{1, 2, 4, 8}$, $\set{3, 6}$, $\set{5, 10}$, $\set{7}$, $\set{9}$ are $5$ chains that cover it. The number $w$ is called the width of $P$. The theorem also holds for an infinite partially ordered set of finite width $w$. The dual result, Mirsky's theorem, says that the largest size of a chain equals the least number of antichains that cover $P$.

Going deeper

For a student

Dilworth's theorem is one of the min-max theorems of combinatorics, like Kőnig's theorem and Menger's theorem, and each of these can be derived from the others. It gives a quick proof of the Erdős–Szekeres theorem: a sequence of $rs + 1$ distinct real numbers has an increasing subsequence of length $r + 1$ or a decreasing subsequence of length $s + 1$. In algorithms, a minimum chain partition of a finite poset can be computed through a maximum matching in a bipartite graph.