Jump number problem: The role of matroids

DOI10.1007/BF00337919MaRDI QIDQ1057289zbMATH OpenOpenAlexFDO

Authors Mirosław Truszczyński

Publication date 1985

Published in Order (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf00337919

zbMATH Keywords

greedylinear extensionsmatroidnumber of jumpsoptimalRado-Edmonds theoremRival's Theorem

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Partial orders, general (06A06)

Review text

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.

Recommendations

• scientific article; zbMATH DE number 952655
• The joints problem for matroids
• scientific article; zbMATH DE number 3896963
• Matroid Parity and Jump Systems: A Solution to a Conjecture of Recski
• The jump number problem: exact and parameterized
• Maximum and minimum jump number of posets from matrices
• On the number of matroids
• On the number of matroids
• On the Complexity of Some Enumeration Problems for Matroids
• scientific article; zbMATH DE number 3370358

Cites work

• Algorithmic Approaches to Setup Minimization
• scientific article; zbMATH DE number 3860892 (Why is no real title available?)
• scientific article; zbMATH DE number 3641455 (Why is no real title available?)
• Minimizing completion time for a class of scheduling problems
• Minimizing Setups for Cycle-Free Ordered Sets
• Minimizing Setups for Ordered Sets: A Linear Algebraic Approach
• Minimizing setups in ordered sets of fixed width
• Minimizing the jump number for partially ordered sets: A graph-theoretic approach
• On the size of jump-critical ordered sets
• Optimal Linear Extensions by Interchanging Chains
• The Jump Number of Dags and Posets: An Introduction

Cited in

(5)

• Minimizing bumps in linear extensions of ordered sets
• Greedy posets for the bump-minimizing problem
• The setup polyhedron of series-parallel posets
• scientific article; zbMATH DE number 952655 (Why is no real title available?)
• The jump number and the lattice of maximal antichains

This page was built for publication: Jump number problem: The role of matroids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1057289)