On the duality of semiantichains and unichain coverings. (Q5965139)

From MaRDI portal
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
    0 references
    0 references
    0 references
    0 references
    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
    0 references
    products of posets
    0 references
    unichain coverings
    0 references
    semiantichains
    0 references
    poset duality
    0 references
    Saks-West conjecture
    0 references
    0 references