Dilworth's theorem (chain/antichain decomposition of a poset) and its dual, Mirsky's theorem

Statement

Dilworth's theorem (R. P. Dilworth, "A Decomposition Theorem for Partially Ordered Sets," *Ann. of Math.* 51(1) (1950), 161–166): in any finite partially ordered set $P$, the maximum size of an antichain (a subset of pairwise-incomparable elements) equals the minimum number of chains (totally-ordered subsets) needed to partition $P$. This common value is the width of $P$ (en.wikipedia.org/wiki/Dilworth's_theorem).

- One direction is trivial: if $A\subseteq P$ is an antichain of size $k$, any chain contains at most one element of $A$, so any chain partition needs $\ge k$ parts. The theorem's content is the converse: a chain partition into exactly (max-antichain-size) parts *always exists* — no partition ever needs *more* chains than the width forces.

Mirsky's theorem (dual): in any finite poset $P$, the maximum size of a chain (equivalently, the *height* of $P$) equals the minimum number of antichains needed to partition $P$ (en.wikipedia.org/wiki/Mirsky's_theorem). This direction is the easy one to prove directly (see Technique below); Dilworth's theorem is "more difficult to prove."

Pigeonhole / Erdős–Szekeres corollary (the form actually used in proofs — a joint consequence of Mirsky's theorem plus counting, or equivalently of Dilworth's theorem plus counting): if $|P| > (r-1)(s-1)$, then $P$ contains either a chain of size $\ge r$ or an antichain of size $\ge s$. Proof via Mirsky: if the longest chain has size $<r$, Mirsky's theorem partitions $P$ into $\le r-1$ antichains, so by pigeonhole some antichain has size $\ge |P|/(r-1) > s-1$, i.e. $\ge s$. (Symmetric proof via Dilworth, partitioning into chains instead.) This exact template — split $|P|$ unevenly between a chain-size guarantee and an antichain-size guarantee via a single real parameter $\alpha$ — is what Andrew Suk's 2017 proof uses (see Facts/Technique).

König's-theorem equivalence: Dilworth's theorem for a finite poset $P$ is equivalent to König's theorem on bipartite graphs. Build a bipartite graph on two copies $U,V$ of the elements of $P$, with an edge $(u,v)$ whenever $u<v$ in $P$; a maximum matching in this graph corresponds to a chain partition using $|P|-(\text{matching size})$ chains, and by König's theorem the matching's complement-of-vertex-cover yields a maximum antichain of exactly that size (en.wikipedia.org/wiki/Dilworth's_theorem). This is also what makes the theorem algorithmically constructive: both the optimal chain decomposition and the maximum antichain are computable in polynomial time via maximum bipartite matching (Hopcroft–Karp etc.), not merely known to exist.

Infinite generalization: a poset of finite width $w$ can *always* be partitioned into exactly $w$ chains (the finite proof extends). But if the width itself is infinite, the theorem can fail badly: for every infinite cardinal $\kappa$ there is a poset of width $\aleph_0$ whose minimum chain partition needs $\kappa$ chains (en.wikipedia.org/wiki/Dilworth's_theorem) — so "finite width" (not just "finite/infinite cardinality") is the exact hypothesis needed, and extending Dilworth to genuinely infinite-width settings requires extra machinery (compactness-type arguments; cf. De Bruijn–Erdős compactness theorem — infinite chromatic number is determined by finite subgraphs).

Comparability-graph / perfect-graph framing: turn a poset $P$ into its *comparability graph* $G$ (vertices = elements, edge = comparable pair). Mirsky's theorem restated says every comparability graph is *perfect* (chromatic number = clique number, hereditarily); Dilworth's theorem restated says the *complement* of every comparability graph is perfect (Berge & Chvátal, *Topics on Perfect Graphs*, Ann. Discrete Math. 21, 1984) — both are special cases of the general perfect-graph phenomenon.

Facts

- Original source: R. P. Dilworth, *Ann. of Math.* 51(1) (1950), 161–166. - Proof mechanism (finite case): Galvin's 1994 inductive proof removes a maximal element $a$, applies induction to get a chain decomposition of $P\setminus\{a\}$ into $k$ chains realizing a max antichain of size $k$, then either slots $a$ into an existing chain (if $a$ is comparable to some element of the witnessing antichain) or starts a new singleton chain $\{a\}$ (if $a$ is incomparable to the whole antichain, which forces the antichain-plus-$a$ to still have size $k$, or $k+1$, consistently) (en.wikipedia.org/wiki/Dilworth's_theorem). Equivalently, one gets the same result for free from König's/Hall's bipartite-matching theorem via the two-copy comparability-graph construction above — this is the route that also makes it *efficiently computable*. - Mirsky's theorem proof mechanism: for each $x\in P$ let $N(x)$ = length of the longest chain with maximum element $x$. Elements with the same $N$-value form an antichain (any two comparable elements $x<y$ must have $N(x)<N(y)$), and the number of distinct $N$-values equals the length of the longest chain — giving the antichain partition directly, no induction or matching needed. This asymmetry (Mirsky = easy direct layering argument; Dilworth = needs induction or an equivalent matching theorem) is why the two are usually presented as a pair rather than treated as interchangeable. - Erdős–Szekeres monotone-subsequence theorem as the canonical illustration: given a sequence of $rs+1$ distinct real numbers, define a poset on the sequence positions by $i\preceq j$ iff $i\le j$ (as indices) *and* $a_i\le a_j$ (as values). A chain in this poset is exactly a (weakly) increasing subsequence; an antichain is exactly a strictly decreasing subsequence. By the pigeonhole corollary above (with $|P|=rs+1>(r-1)(s-1)$… more precisely the classical count uses $rs+1$ points to force a chain of length $r+1$ or antichain of length $s+1$), either an increasing subsequence of length $r+1$ or a decreasing one of length $s+1$ exists (en.wikipedia.org/wiki/Mirsky's_theorem, citing J. M. Steele, "Variations on the monotone subsequence theme of Erdős and Szekeres," IMA Vol. 72, Springer 1995). This is the standard *textbook* second proof of Erdős–Szekeres (the first being the direct $(a(i),b(i))$-pair pigeonhole argument) — it is the template Suk's 2017 proof scales up geometrically (next bullet). - Concrete worked modern application (Andrew Suk, "On the Erdős-Szekeres convex polygon problem," *J. Amer. Math. Soc.* 30 (2017), 1047–1053, arXiv:1604.08657 — read in full): proves $ES(n)=2^{n+o(n)}$, nearly settling the 1935/1960 Erdős–Szekeres convex-polygon conjecture (Erdős #107 — exact Erdős–Szekeres convex-polygon constant). Inside a Pór–Valtr "support region" $P_i$ around a partial cup/cap $X$, Suk defines the partial order $p\prec q \iff p\ne q \text{ and } q\in\mathrm{conv}(B_i\cup p)$ (roughly: $q$ is "seen" from $p$ across the fixed chord $B_i$). Setting $\alpha=3n^{-1/3}\log n$, "By Dilworth's Theorem [4], $P_i$ contains either a chain of size at least $|P_i|^{1-\alpha}$ or an antichain of size at least $|P_i|^{\alpha}$" (arXiv:1604.08657v2, p.3, exact quote) — this is precisely the pigeonhole corollary above, applied with an *asymmetric, tunable* split ($1-\alpha$ vs. $\alpha$) rather than a fixed $m,n$. The two cases are then finished geometrically: an antichain in $\prec$ turns out to correspond to a subset whose pairwise-spanned lines all avoid the chord $B_i$, so several such antichains from non-adjacent regions can be unioned into one big cap (Case 1); a chain in $\prec$ turns out to correspond to a subset that is a "left-cap or right-cap" (a rotated cup/cap), so consecutive chains can be stitched together into one long cap via an explicit convex-position lemma (Case 2, Observation 3.1). Both cases bottom out in one final application of the classical Erdős–Szekeres cup–cap theorem (Theorem 2.2 there) to close the induction. This is the single concrete mechanism (not the textbook monotone-subsequence proof) that earns Dilworth's theorem a place in the current state-of-the-art bound for Erdős #107 — exact Erdős–Szekeres convex-polygon constant. - Computability: because of the König/Hall-matching equivalence, both the minimum chain decomposition and the maximum antichain of a finite poset are computable in polynomial time (via maximum bipartite matching) — Dilworth's theorem is not merely an existence statement, it is algorithmically tight and constructive. - Do not confuse with the Mirsky–Newman theorem (a different, unrelated theorem also involving a "Mirsky," about integer covering systems having no exact/disjoint distinct-modulus cover — see Erdős #2 — minimum modulus of a covering system cannot be arbitrarily large's Facts) — same mathematician, Leon Mirsky, but a distinct 1958 result with no direct chain/antichain content.

Technique

WHEN it applies: any extremal question of the shape "how large must a monotone / pairwise-related structure be, given a bound on the pairwise-unrelated structure (or vice versa), inside $N$ objects carrying a natural partial order" — monotone subsequences, nested families (chains of sets under $\subseteq$), sequences of "compatible" geometric objects (points seen in increasing convex-position order, as in Suk's proof), divisibility antichains (cf. Erdős #123 — three coprime bases give a d-complete set?'s $d$-completeness, though that problem's antichain condition is about the *conclusion*, not proved via Dilworth), and more generally any two-coloring/Ramsey-style dichotomy where one side is naturally "totally ordered" and the other "pairwise incomparable" under some induced relation.

WHY it works (the mechanism): the theorem is really a max-flow/min-cut (equivalently LP-duality) statement in disguise — comparability edges of a poset form a bipartite graph (via the two-copy construction) with no integrality gap between maximum matching and minimum vertex cover (König's theorem), and this integrality gap-freeness is exactly what forces "min chains to cover = max antichain" rather than merely "min chains to cover $\ge$ max antichain" (the trivial direction). No clever combinatorial luck is needed beyond the fact that comparability graphs are always bipartite-matching-tight; this is also why the theorem generalizes so cleanly to a *computationally exact* algorithm rather than staying a pure existence result.

HOW to use it to prove things (recombination steps): 1. Engineer a partial order on your objects so that the structure you want ("increasing run," "nested family," "pairwise-compatible geometric configuration") is *exactly* a chain, and the complementary/obstructing structure ("decreasing run," "pairwise-incompatible set") is exactly an antichain. This reduction step is the real creative work — Dilworth's theorem itself is then a black box. 2. Bound the poset's size $|P|=N$ (or lower-bound it, as in an extremal/Ramsey-type argument). 3. Apply the pigeonhole corollary with a chosen split — either a fixed $(r,s)$ with $N>(r-1)(s-1)$ (classical Erdős–Szekeres form), or, for finer asymptotic control, a tunable real exponent split as in Suk's $|P_i|^{1-\alpha}$ vs. $|P_i|^\alpha$ — to conclude "chain of size $\ge X$ or antichain of size $\ge Y$." 4. Handle the two cases separately, translating "chain" and "antichain" back into the language of the original problem (monotone subsequence; convex cap; nested family) and finishing each branch with problem-specific glue (in Suk's proof: the non-adjacency-of-support-regions argument glues several antichains into one cap; the left-cap/right-cap dichotomy plus Observation 3.1 glues several chains into one cap). The theorem supplies the dichotomy; it never by itself finishes the geometric/combinatorial argument — expect a nontrivial "reassembly" step after invoking it. 5. When the poset is genuinely infinite with infinite width, do not invoke Dilworth's theorem directly — reach instead for a compactness-style argument (De Bruijn–Erdős-style, see De Bruijn–Erdős compactness theorem — infinite chromatic number is determined by finite subgraphs) to bootstrap from the finite theorem, and check the infinite-width counterexamples don't apply to your setting first.

Concrete worked examples on file in this wiki: - Classical: partial order $i\preceq j \iff i\le j \text{ and } a_i\le a_j$ on a real sequence; chains = increasing subsequences, antichains = decreasing subsequences; textbook second proof of the Erdős–Szekeres monotone-subsequence theorem (Steele 1995). - Modern/frontier: Erdős #107 — exact Erdős–Szekeres convex-polygon constant — Suk's 2017 near-resolution of the Erdős–Szekeres convex-polygon conjecture applies Dilworth's theorem to the partial order $p\prec q\iff q\in\mathrm{conv}(B_i\cup p)$ on each Pór–Valtr support region, splitting $|P_i|^{1-\alpha}$ (chain) vs. $|P_i|^\alpha$ (antichain), then reassembles either output into a single large cap via geometric lemmas — this is the exact mechanism that pushed the base of the exponent from $4$ to $2$.

Related

- Erdős #107 — exact Erdős–Szekeres convex-polygon constant — Erdős–Szekeres convex-polygon problem: Suk's 2017 near-resolution ($ES(n)=2^{n+o(n)}$) applies Dilworth's theorem to a partial order on each Pór–Valtr support region as one of its three core tools (alongside the cup–cap theorem and the positive-fraction Erdős–Szekeres theorem). - De Bruijn–Erdős compactness theorem — infinite chromatic number is determined by finite subgraphs — the compactness technique needed to extend finite-poset results (Dilworth's theorem included) to genuinely infinite-width posets, where the naive finite statement can fail. - Erdős #2 — minimum modulus of a covering system cannot be arbitrarily large — covering systems; not related to Dilworth's theorem despite the name overlap — flagged here only to disambiguate from the unrelated Mirsky–Newman theorem (also due to Leon Mirsky) used there. - Concepts referenced but not yet their own pages: "cup-cap theorem" / `Erdős–Szekeres cup-cap (cap-cup) theorem: exact Ramsey number for convex chains and "positive-fraction Erdős–Szekeres theorem" / Pór–Valtr positive-fraction Erdős–Szekeres theorem: dense clusters, not just points, in convex position` — the two companion tools alongside Dilworth's theorem in Suk's Erdős #107 — exact Erdős–Szekeres convex-polygon constant proof (already forward-linked from problems/107.md).