On the duality of semiantichains and unichain coverings. (Q5965139): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 00:50, 5 March 2024
scientific article; zbMATH DE number 6548274
Language | Label | Description | Also known as |
---|---|---|---|
English | On the duality of semiantichains and unichain coverings. |
scientific article; zbMATH DE number 6548274 |
Statements
On the duality of semiantichains and unichain coverings. (English)
0 references
2 March 2016
0 references
A min-max conjecture of Saks and West states that in every product \(P\times Q\) of two posets, the size of the largest semiantichain equals the size of the smallest unichain covering. A counterexample to this conjecture with \(9\times 3=27\) elements is exhibited and it is the only one with size 27 or less. Moreover, it is shown that the size of the gap between the two sizes can be, in general, arbitrarily high. On the other side, the validity of the conjecture is shown in other cases, like: 1. When \(P\) and \(Q\) have height at most 2. 2. When \(P\) is ``rectangular'' and \(Q\) is an arbitrary poset. -- A new framework which uses the concepts of c- and d-decomposability of posets is provided, as well.
0 references
products of posets
0 references
unichain coverings
0 references
semiantichains
0 references
poset duality
0 references
Saks-West conjecture
0 references