Greedy linear extensions to minimize jumps (Q1061150): Difference between revisions

The problem of linear extensions of (partially) ordered sets has received much attention lately. Let P be an ordered set of n elements and L(P) the set of all its linear extensions, i.e. linear (total) orders on P respecting the given order relation. A ''jump'' is the occurence of two elements p,q in a linear extension, p covering q, but \(p\ngeq q\) in the original order. Call S(P) the minimal number of jumps taken over L(P). A linear extension of P is called optimal if its number of jumps is equal to S(P). Among others, there are two main problems concerning S(P) and O(P): find an algorithm to determine S(P) and one for constructing elements of O(P). The first problem has recently been shown to be NP-hard by W. R. Pulleyblank. For the second problem, one has devised a greedy algorithm, leading to a set G(P) of linear extensions of P. In general neither of O(P) and G(P) need contain the other, so it becomes an important question to find conditions for P that allow statements about the connection between O(P) and G(P). The second author has proved that \(G(P)=O(P)\) in case P is N-free, where N is a well-known ordered set of 4 elements. The present paper shows in Theorem 1 that O(P)\(\subseteq G(P)\) in case P does not contain an ordered \(2n+1\)-set usually called a ''fence''. Two other theorems are concerned with combinatorial rather than algorithmic problems. It is very unfortunate that the authors use the letter \(C_ n\) for n- chains (as usual), but also for the exceptional sets mentioned above. This makes reading of their paper especially troublesome.