Dilworth's Theorem

Dilworth's theorem is not an isolated curiosity; it is one node in a web of combinatorial min-max theorems. Via a standard bipartite-graph encoding — split each element of $P$ into a "left copy" and "right copy," join $x_{\text{left}}$ to $y_{\text{right}}$ whenever $x < y$ — a chain partition into $k$ chains corresponds to a perfect matching argument, and Dilworth's theorem becomes a corollary of König's theorem on minimum vertex covers in bipartite graphs, and hence ultimately of the max-flow min-cut theorem in network flow theory. This connection means efficient algorithms for bipartite matching (such as the Hopcroft–Karp algorithm) yield polynomial-time algorithms for computing a minimum chain cover of a poset. In algebraic combinatorics, the Robinson–Schensted correspondence and the Greene–Kleitman theorem generalize Dilworth's theorem: they show that the sizes of the longest increasing/decreasing subsequences and unions thereof, for a permutation viewed as a poset, are governed by the shape of an associated Young tableau, refining Dilworth's and Mirsky's theorems simultaneously. This is a direct forerunner of ideas used in the construction of combinatorial designs, where covering and packing numbers of structured set systems are studied with the same min-max philosophy: an easy inequality from a natural obstruction, matched by a hard-won construction achieving equality. In scheduling theory, Dilworth's theorem answers precisely the "minimum number of machines" question from the overview: if jobs have precedence constraints forming a poset, the minimum number of machines needed (each processing an increasing sequence of pairwise-compatible jobs) equals the maximum number of pairwise-incompatible (mutually unschedulable in sequence) jobs. In statistics and probability, Dilworth-type decompositions appear in the study of partial orders on data and in reliability theory. In theoretical computer science, the theorem underlies algorithms for interval scheduling, comparability graph recognition, and the perfect graph theory of comparability graphs (where clique cover number equals independence number, a direct graph-theoretic restatement of Dilworth's theorem, since chains become cliques and antichains become independent sets in the comparability graph of $P$).

Ask the tutor: How does the bipartite-matching encoding turn Dilworth's theorem into a direct corollary of König's theorem?

Think of $P$ as a directed acyclic diagram — its Hasse diagram — where an edge from $x$ up to $y$ means $x < y$ and no element sits strictly between them. A chain is a path that climbs monotonically through this diagram, possibly skipping levels; an antichain is a set of elements no two of which are joined by any climbing path at all, i.e. a "horizontal slice" of mutual incomparability. Covering the poset by chains is like assigning every element to one of $k$ climbers, each climber's assigned elements forming a single increasing trail. If the poset contains an antichain of size $w$, then no matter how you organize climbers, each of the $w$ mutually incomparable elements must belong to a different climber's trail, since a single trail is totally ordered and cannot contain two incomparable elements. This forces $k \ge w$: the max antichain is a lower bound on the number of chains needed. The surprising content of Dilworth's theorem is that this obvious obstruction is the only obstruction — you can always achieve $k = w$ exactly. The picture below shows a small poset with six elements. The widest antichain has size $3$ (the middle level), and indeed the poset can be partitioned into exactly $3$ chains, matched color-for-color with the three antichain elements they pass through.

The width-$3$ antichain $\{y_1, y_2, y_3\}$ is a certificate that no fewer than $3$ chains can suffice, and the $3$ colors show a matching partition of the whole poset into $3$ chains $\{x_1, y_1, z_1\}$, $\{x_2, y_2, z_2\}$, $\{x_3, y_3, z_3\}$. Dilworth's theorem says this coincidence of "obstruction size" and "cover size" is never an accident: it always happens.

Example 1: The divisibility poset on $\{2,3,4,5,6,7,9,10,12,15,25\}$. Let $X = \{2,3,4,5,6,7,9,10,12,15,25\}$ ordered by divisibility ($x \le y$ iff $x \mid y$). We compute $c(P)$ and $a(P)$ directly and check they match. First, find a large antichain. The primes-and-prime-squares-and-products-of-two-distinct-primes tend to be mutually non-dividing when none divides another. Consider

Check pairwise: $4\nmid 6, 6\nmid4$; $4\nmid9,9\nmid4$; $4\nmid10$; $4\nmid15$; $4\nmid25$; $6\nmid9,9\nmid6$; $6\nmid10,10\nmid6$; $6\nmid15,15\nmid6$; $6\nmid25$; $9\nmid10$; $9\nmid15,15\nmid9$; $9\nmid25$; $10\nmid15,15\nmid10$; $10\nmid25,25\nmid10$; $15\nmid25,25\nmid15$. All six elements are pairwise incomparable, so $a(P) \ge 6$. Could $a(P) \ge 7$? Any antichain can include at most one of $\{2,4\}$ (since $2\mid4$), at most one of $\{2,6,10\}$ pairwise chains through $2$, and more usefully we bound by exhibiting a chain cover of size $6$ and invoking Step 1 of the theorem to pin down equality. Partition $X$ into six chains:

Correct $C_6$: $15$ and $25$ are incomparable ($15\nmid25$, $25\nmid15$), so they cannot form a chain. Redo the chain cover carefully. Divisibility relations present in $X$: $2\mid4\mid12$; $2\mid6\mid12$; $2\mid10$; $3\mid6\mid12$; $3\mid9\mid...$ ($9 \nmid$ anything else in $X$); $3\mid15$; $5\mid10$; $5\mid15$; $5\mid25$. A valid chain partition into $6$ chains:

This uses $7$ chains, not $6$ — let's improve it. Since $5 \mid 15$ and $5\mid25$ but $15,25$ incomparable, $5$ can only be paired with one of them in a chain. Try:

Since $6$ divides $12$ and $3,2$ both divide $6$, but $12$ already used by $\{2,4,12\}$, we can instead route $6$ through the chain with $3$: $3\mid6$, and does $6$ divide anything else free? $6\mid12$ but $12$ taken. Try:

Still $7$ chains since $4,7,15,25$ are singletons alongside three longer chains — that's $3+4=7$ chains covering $3+2+1+2+1+1+1=11$ elements. Correct, $|X|=11$. To get down to $6$ chains we'd need average chain length $11/6 \approx 1.83$; but we have $6$ "leftover" elements ($4,7,9,15,25$, and one of $6$) that resist merging further given the antichain of size $6$ found above forces at least $6$ chains, and we should check whether $6$ is achievable or the true width is actually $7$. Re-examine: is $\{4,6,9,10,15,25\}$ really of maximum size, or is there a 7-element antichain? Try adding $7$: is $7$ comparable to any of $4,6,9,10,15,25$? No ($7$ is prime, none of the others is a multiple of $7$ within $X$, since $14,21,28,35$ are not in $X$). So

is an antichain of size $7$! Check all pairs again: all pairs among $\{4,6,9,10,15,25\}$ were already verified incomparable, and $7$ is incomparable to each of them since $7 \nmid 4,6,9,10,15,25$ and none of those divides $7$. So $a(P) \ge 7$. Now by Dilworth's theorem $c(P) = a(P) \geq 7$, matching our chain cover of size $7$ found above:

Since this is a valid partition into $7$ chains and we found an antichain of size $7$, both bounds meet: $c(P) = a(P) = 7$. This matches the theorem exactly, and illustrates how easy it is to undercount the true width by stopping the search for a bigger antichain too early — the theorem's guarantee that the two numbers must coincide is precisely what tells us to keep searching until a matching chain cover is found.

Example 2: A "zigzag" (fence) poset of width computed from a non-obvious antichain. Let $X = \{a_1,a_2,a_3,a_4,b_1,b_2,b_3\}$ with covering relations $a_1<b_1$, $a_2<b_1$, $a_2<b_2$, $a_3<b_2$, $a_3<b_3$, $a_4<b_3$ (a "fence" zigzag), and no other relations (so e.g. $a_1, a_3$ are incomparable, $b_1,b_2$ incomparable, etc.). This models a bipartite-like poset with $4$ minimal elements and $3$ maximal elements arranged in a path pattern. Finding the width. The set of all minimal elements $\{a_1,a_2,a_3,a_4\}$ is an antichain (no $a_i < a_j$ by construction), of size $4$. Could there be a larger antichain? The whole poset has only $7$ elements, and $\{a_1,a_2,a_3,a_4\}\cup\{b_i\}$ for any $b_i$ would fail since each $b_i$ is above two of the $a_j$'s, so adding any $b_i$ creates a comparable pair. Mixing some $b$'s in place of some $a$'s: e.g. $\{a_1, b_2, a_4\}$ — check $a_1$ vs $b_2$: incomparable (since $a_1<b_1$ only); $a_1$ vs $a_4$: incomparable; $b_2$ vs $a_4$: incomparable (since $b_2 > a_2,a_3$ only). This gives size $3$, smaller. So $a(P)=4$, realized uniquely (up to this construction) by the minimal-element level. Finding a matching chain cover. We need $4$ chains covering all $7$ elements. Take:

Check: $a_1<b_1$ ✓ chain; $a_2<b_2$ ✓ chain (note $a_2 < b_1$ also holds but we don't need it here); $a_3<b_3$ ✓ chain; $a_4$ alone is trivially a chain. These four sets cover all $7$ elements exactly once, so this is a partition into $4$ chains. Since $a(P)=4 \le c(P)$ by Step 1, and we exhibited $c(P)\le4$, we conclude $c(P)=4=a(P)$, confirming Dilworth's theorem on this example and showing that the "greedy" chain choice $C_1=\{a_1,b_1\}$ does not need to use the alternative edge $a_2<b_1$; multiple valid chain covers of the minimum size can coexist. By Mirsky's dual theorem, we can also decompose $X$ into antichains according to longest-chain-ending-here rank: $r(a_i)=1$ for all $i$ (no element below them), and $r(b_j) = 2$ for all $j$ (longest chain ending at $b_j$ has length $2$, e.g. $a_2<b_2$). So the antichain partition is $A_1 = \{a_1,a_2,a_3,a_4\}$, $A_2=\{b_1,b_2,b_3\}$, using $2$ antichains — matching the longest chain length of $2$ in this poset (e.g. $a_1<b_1$ has length $2$, and no chain in this poset has length $3$ since every chain alternates at most one $a$ and one $b$).