Mirsky's Theorem states that the minimum number of chains needed to cover every element of a finite partially ordered set exactly equals the size of the set's longest antichain, a collection of elements no two of which are comparable to each other. Named for Leon Mirsky, it is the order-theoretic dual of Dilworth's Theorem, which gives the same equality with the roles of chains and antichains reversed.
Facts
StatementFor every finite partially ordered set, the height equals the minimum number of antichains into which the set may be partitioned. 1 Classification
Statement Form Connections
Has Statement Form
In Branch
Source Mirsky's theorem (Wikipedia)
Principal Result Of
Source Leonid Mirsky (Wikipedia)
Proved By
Source Mirsky's theorem (Wikipedia)
Sources
1. Mirsky's theorem (Wikipedia)
The theorem
Mirsky's theorem states that, for every finite partially ordered set, the height also equals the minimum number of antichains (subsets in which no pair of elements are ordered) into which the set may be partitioned.
Naming attribution
It is named for Leon Mirsky (1971).
Proved By: Leon Mirsky, Lead sentence
It is named for Leon Mirsky (1971) and is closely related to Dilworth's theorem on the widths of partial orders, to the perfection of comparability graphs, to the Gallai-Hasse-Roy-Vitaver theorem relating longest paths and colorings in graphs, and to the Erdős-Szekeres theorem on monotonic subsequences.
In Branch: Combinatorics, Lead sentence
In mathematics, in the areas of order theory and combinatorics, Mirsky's theorem characterizes the height of any finite partially
In Group: Enumerative, Additive and Algebraic Combinatorics, Lead section
In mathematics, in the areas of order theory and combinatorics, Mirsky's theorem characterizes the height of
View the SourceLeonid Mirsky (Wikipedia)
Principal Result Of: Leon Mirsky, LeadQuote, Principal Result Of: Leon Mirsky, Lead
Mirsky's theorem is named after him.
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.