Another proof of Dilworth's decomposition theorem (Q1252854): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A decomposition theorem for partially ordered sets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3274165 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Note on Dilworth's Decomposition Theorem for Partially Ordered Sets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A proof of Dilworth's decomposition theorem for partially ordered sets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On Dilworth's decomposition theorem for partially ordered sets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The structure of Sperner k-families / rank | |||
Normal rank |
Latest revision as of 00:59, 13 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Another proof of Dilworth's decomposition theorem |
scientific article |
Statements
Another proof of Dilworth's decomposition theorem (English)
0 references
1979
0 references
This note gives a new proof of Dilworth's famous Theorem: ``If a partially ordered set \(S\) has maximal sized antichains with \(n\) elements, then \(S\) can be covered by \(n\) chains''. The proof differs from earlier ones in that the chains are constructed one by one. A method is described that starting with a minimal element of the set successively adjoins one element at a time to construct a sequence of chains that has the property that each maximal sized antichain that does not intersect \(C\) contains an element lying above all elements of \(C\). The maximal chain \(C\) thus constructed intersects all antichains of maximal size and so its removal reduces the width of \(S\).
0 references
partially ordered set
0 references
Dilworth's decomposition theorem
0 references
covering
0 references
maximal sized antichains
0 references