Jump number problem: The role of matroids
type: Item
instance of: scholarly article
title: Jump number problem: The role of matroids
zbMATH Open document ID: 0563.06001
DOI: 10.1007/BF00337919
published in: Order
publication date: 1985-01-01T00:00:00Z
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.
Mathematics Subject Classification ID: 06A06
Mathematics Subject Classification ID: 05B35
zbMATH DE Number: 3896985
zbMATH Keywords: number of jumps
zbMATH Keywords: linear extensions
zbMATH Keywords: optimal
zbMATH Keywords: greedy
zbMATH Keywords: Rival's Theorem
zbMATH Keywords: matroid
zbMATH Keywords: Rado-Edmonds theorem
author: Mirosław Truszczyński
reviewed by: J. Neggers
MaRDI profile type: Publication
cites work: The Jump Number of Dags and Posets: An Introduction
cites work: Q4200070
cites work: Minimizing setups in ordered sets of fixed width
cites work: Minimizing Setups for Cycle-Free Ordered Sets
cites work: On the size of jump-critical ordered sets
cites work: Algorithmic Approaches to Setup Minimization
cites work: Q3329227
cites work: Minimizing completion time for a class of scheduling problems
cites work: Minimizing Setups for Ordered Sets: A Linear Algebraic Approach
cites work: Optimal Linear Extensions by Interchanging Chains
cites work: Minimizing the jump number for partially ordered sets: A graph-theoretic approach
full work available at URL: https://doi.org/10.1007/bf00337919
OpenAlex ID: W1974931478
Recommended article: Q4717614
Recommended article: The joints problem for matroids
Recommended article: Q3676161
Recommended article: Matroid Parity and Jump Systems: A Solution to a Conjecture of Recski
Recommended article: The Jump Number Problem: Exact and Parameterized
Recommended article: Maximum and minimum jump number of posets from matrices
Recommended article: On the number of matroids
Recommended article: On the Complexity of Some Enumeration Problems for Matroids
Recommended article: Q5642579
description: scientific article; zbMATH DE number 3896985