Greedy linear extensions with constraints (Q1821122)

From MaRDI portal





scientific article; zbMATH DE number 3997854
Language Label Description Also known as
English
Greedy linear extensions with constraints
scientific article; zbMATH DE number 3997854

    Statements

    Greedy linear extensions with constraints (English)
    0 references
    0 references
    0 references
    1987
    0 references
    Given a poset P, a greedy linear extension L of P is obtained algorithmically according to the rule: ''Climb as high as you can'' (and still be able to extend linearly by scheduling remaining vertices to appear even higher). If P is a W-free poset then the authors show that (1) for every anti-chain \(\{a_ 1,...,a_ n\}\), \(n\geq 2\) in P, there is a greedy linear extension L of P such that \(a_ 1\leq a_ 2<...<a_ n\) (in L). They also show (2) that in this case \(\dim_ gP\), the minimum number of greedy linear extensions whose intersection is P, equals dim P, thus generalizing from the smaller class of N-free posets. As the authors of this nicely written paper containing many good techniques and useful observations note, there are posets which are not W-free which also have the property given in (1), begging the question whether there is indeed a characteristic superposet of W which must be absent in order for (1) to hold. Answers are bound to be most interesting.
    0 references
    N-free poset
    0 references
    greedy linear extension
    0 references
    W-free poset
    0 references
    0 references

    Identifiers