Jump number problem: The role of matroids
If \(L=\{x_ 1<x_ 2<...<x_ n\}\) is a linear extension of the poset P with vertices \(x_ 1,...,x_ n\), then \(x_ i<x_ j\) in P implies \(i<j\). If \(x_{i+1}\) is a minimal element of \(P\setminus \{x_ 1,...,x_ i\}\) which covers \(x_ i\) when possible, then L is greedy. If the number of jumps \(x_ i\nless x_{i+1}\) in P is as small as possible then L is optimal. Rival's Theorem states that if P is N-free then linear extensions are optimal if and only if they are greedy. In this paper the author proves a converse to Rival's Theorem. He accomplishes this by reproving a generalization of Rival's Theorem due to Faigle and Schrader and its converse using matroid theoretic methods and the Rado-Edmonds theorem. Given the importance of all results involved this is a very nice paper although the referee(s) could have added points of style.
scientific article; zbMATH DE number 3896985
scientific article