Dilworth Theorem

Dilworth's theorem is a cornerstone result in combinatorial order theory, establishing a fundamental duality between chains and antichains. It connects poset structure to graph theory and has numerous applications in scheduling, optimization, and algebra.

TheoremDilworth's Theorem

Let $P$ be a finite poset with width $w$ (maximum antichain size). Then $P$ can be partitioned into $w$ chains, and no fewer chains suffice. Equivalently: $\min\{\text{number of chains covering } P\} = \max\{\text{size of antichain in } P\}$

ProofVia Kőnig's Theorem

We construct a bipartite graph $G = (P \cup P', E)$ where $P'$ is a copy of $P$ and $(x,y') \in E$ iff $x < y$ in $P$ .

A chain cover of $P$ corresponds to a matching in $G$ : each chain uses edges connecting consecutive elements. A maximum matching gives a minimum chain cover.

By Kőnig's theorem, the size of a maximum matching equals the size of a minimum vertex cover. An antichain $A$ in $P$ gives a vertex cover $A \cup (P' \setminus A')$ (no edge from $A$ to $P' \setminus A'$ since antichain elements are incomparable).

Conversely, any minimum vertex cover corresponds to an antichain. Thus: $\text{max matching} = \text{min vertex cover} = \text{max antichain}$

■

ExampleApplication

In a divisibility poset on $\{1,2,\ldots,12\}$ :

Primes $\{2,3,5,7,11\}$ form antichain of size 5
Minimum chain cover uses 5 chains:
- $1 < 2 < 4 < 8$
- $3 < 6 < 12$
- $5 < 10$
- $7$
- $11$

Remark

Dilworth's theorem has applications in:

Scheduling: minimize number of processors
Dimension theory: Dushnik-Miller dimension of posets
Representation theory: decomposing modules
Extremal set theory: proving combinatorial inequalities

This theorem exemplifies deep connections between order theory, graph theory, and combinatorial optimization.