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
StatementIn 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 Classification
Statement Form Connections
Has Statement Form
In Branch
Proved By
Source Dilworth's Theorem (Wikipedia)
Sources
1. Dilworth's Theorem (Wikipedia)
Wikimedia Foundationlead 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.
Proved By: Robert P. Dilworth, Lead
The theorem is named for the mathematician Robert P. Dilworth, who published it in 1950.
In Group: Enumerative, Additive and Algebraic Combinatorics, Lead section
In mathematics, in the areas of order theory and combinatorics, Dilworth's theorem states that, in any finite
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.