Dilworth's theorem

In every finite partially ordered set, the largest antichain has the same size as the smallest number of chains that partition the set.

Antichain: A subset of a partially ordered set whose distinct elements are pairwise incomparable. The theorem’s maximum is taken over all antichains.
Partially ordered set: A set equipped with a reflexive, antisymmetric, transitive relation. Dilworth’s theorem applies to finite sets with this structure.
Chain partitioning: Dividing a partially ordered set into disjoint chains. The theorem gives the fewest chains required by the poset’s width.
Robert P. Dilworth: An American mathematician known for work in lattice theory and partially ordered sets. He proved the theorem in a 1950 paper on partially ordered sets.
Chain: A subset of a partially ordered set in which every pair of elements is comparable. The theorem’s minimum counts chains in a partition.
Partial order: A reflexive, antisymmetric, transitive binary relation on a set. Comparability under this relation determines membership in chains and antichains.
Partially ordered set scheduling: Scheduling tasks subject to precedence constraints represented by a partial order. Chains represent sequential task paths, while antichains capture simultaneous precedence-free tasks.
Lattice theory: The study of algebraic structures in which pairs of elements have joins and meets. Dilworth’s work on partially ordered sets grew within this mathematical tradition.
Bipartite matching: A set of edges in a bipartite graph with no shared endpoints. A matching construction converts the poset problem into a chain-cover problem.
Comparability graph: A graph joining two distinct elements when they are comparable in a partial order. It represents the poset’s comparable pairs as graph edges.

Linked from 4 pages

Sperner's theoremCompared with: It characterizes antichain width through chain partitions rather than giving a Boolean-lattice rank bound.