Dual of Dilworth's theorem (Mirsky's theorem)
Statement
A dual of Dilworth's theorem states that the size of the largest chain in a partial order (if finite) equals the smallest number of antichains into which the order may be partitioned. This is called Mirsky's theorem. Its proof is much simpler than the proof of Dilworth's theorem itself: for any element x, consider the chains that have x as their largest element, and let N(x) denote the size of the largest of these x-maximal chains. Then each set N−1(i), consisting of elements that have equal values of N, is an antichain, and these antichains partition the partial order into a number of antichains equal to the size of the largest chain.
Further reading
- Wikipedia, page 749033, revision 1305701504, Dilworth's theorem, section Dual of Dilworth's theorem (Mirsky's theorem). adopted
About this page
| Tag | T92G094ATY |
|---|---|
| URI | m2://T92G094ATY |
| Kind | statement, theorem |
| Writing | W0 stub |
| Status | This copy of the site has no build data. Run m2 status T92G094ATY. |
| Changed | 4 November 2026 |
Markdown · JSON · Edit on GitHub
What this page needs for W1
- edge uses out: each definition that the statement needs (0 of 1)
The writing levels say how complete the text of a page is. They do not measure its truth.
What links here
No page links to this page yet.