Theorem

Dilworth's Theorem

Combinatorics and Graph Theory

In any finite partially ordered set, the minimum number of chains needed to cover every element equals the maximum size of an antichain. Proved by Robert Dilworth, it is a foundational duality theorem of order theory and combinatorics, dual to Mirsky's theorem for chains and antichains reversed.

Facts

Statement

In any finite partially ordered set, the maximum size of an antichain of incomparable elements equals the minimum number of chains needed to cover all elements. 1

Proof Year

1950 1

Classification

Statement Form

Existence Theorem 1

Connections

Has Statement Form

Existence Theorem

Entity-backed identity for the statement-form enum value this theorem already carries, resolved to a mathematics concept by an explicit value-to-entity map (phase 3 bucket conversion, docs\design_entity_backed_browse_buckets_20260928.md). The statement-form fact itself stays on the theorem unchanged.

In Branch

Combinatorics

Sources

1. Dilworth's Theorem (Wikipedia)

Wikimedia Foundation

lead paragraph, opening sentence
in any finite partially ordered set, the maximum size of an antichain of incomparable elements equals the minimum number of chains needed to cover all elements
lead paragraph, sentence naming the publication year
The theorem is named for the mathematician Robert P. Dilworth, who published it in 1950.
Lead section, statement-form reference
A version of the theorem for infinite partially ordered sets states that, when there exists a decomposition into finitely many chains, or when there exists a finite upper bound on the size of an antichain, the sizes of the largest antichain and of the smallest chain decomposition are again equal.

Switch Atlas

The Inner World

The Civil World

The Natural World

Dilworth's Theorem

Has Statement Form

In Branch