Greedy linear extensions with constraints (Q1821122)
From MaRDI portal
| This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Greedy linear extensions with constraints |
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
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