Greedy posets for the bump-minimizing problem
type: Item
instance of: scholarly article
title: Greedy posets for the bump-minimizing problem
zbMATH Open document ID: 0636.06002
DOI: 10.1007/BF00337888
author: Nejib Zaguia
published in: Order
publication date: 1987-01-01T00:00:00Z
review text: Given a finite poset P and a linear extension \(L=\{x_ 1<x_ 2<...<x_ n\}\), a bump \((x_ i,x_{i+1})\) occurs if \(x_ i<x_{i+1}\) in P (no covering implied). In contrast, a jump \((x_ i,x_{i+1})\) occurs if \(x_ i\nleq x_{i+1}\) in P. Notice that bumps and jumps are complementary notions once we observe that \(x_ i>x_{i+1}\) is always excluded in P because of the choice of numbering for the vertices. Thus, if \(b(P)=\min \{b(L)/\) L is a linear extension of \(L\}\), where b(L) is the number of bumps of L (relative to P), then determining b(P) amounts not only to minimizing bumps in extensions (or schedules) but maximizing jumps, whereas determining the jump-number is equivalent to the problem of maximizing bumps. In terms of bumps, L is greedy if \((x_ i,x_{i+1})\) in L implies \(x_ i<x_ j\) in P whenever \(i<j\). Greedy posets in this setting are precisely those for which every greedy linear extension has a minimum number of bumps. In this paper the author shows that Thm 3: a poset P is greedy and \(b(P)=0\) iff for every x in \(C_ k\), where \(C_ k=\{x|\) x is minimal in \(P\setminus C_{k-1}\}\), \(C_{-1}=\emptyset\), \(0\leq k\leq n\), \(C_ 0\cup...\cup C_ n=P\), the following properties hold: \[ (i)\quad | \{y\in C_{k+1}| y>x\}| \leq | C_{k+1}| -1 \] \[ (ii)\quad | \{y\in C_{k-1}| y<x\}| \geq | C_{k-1}| -2, \] with equality holding only when \(k>2\), and if for every \(y\in C_{k-1}\) such that \(y<x\), \(\{z\in C_{k-2}| z<y\}=C_{k-2}\). Based on this very useful result and a decomposition theorem due to Al-Thukair and the author (Thm 2: Let P be a greedy poset with \(b(P)=k\). Then \(P=Q_ 0\oplus...\oplus Q_ k\) (\(\oplus\) linear or ordinal sum) where \(Q_ i\) is greedy and \(b(Q_ i)=0\) for every \(i\in \{0,...,k\})\), it follows that there is an effective characterization of greedy posets. The characterization of the greedy posets for the jump-number problem is different and, as the author among others has demonstrated in a great variety of papers, a problem w…
Mathematics Subject Classification ID: 06A06
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 90B35
zbMATH DE Number: 4035885
zbMATH Keywords: finite poset
zbMATH Keywords: linear extension
zbMATH Keywords: bump
zbMATH Keywords: jump
zbMATH Keywords: greedy poset
reviewed by: J. Neggers
MaRDI profile type: Publication
cites work: Greedy linear extensions for minimizing bumps
cites work: Q3890731
cites work: Jump number of dags having Dilworth number 2
cites work: Q4200070
cites work: Minimizing setups in ordered sets of fixed width
cites work: Minimizing Setups for Cycle-Free Ordered Sets
cites work: Greedy linear extensions to minimize jumps
cites work: On the size of jump-critical ordered sets
cites work: Minimizing bumps in linear extensions of ordered sets
cites work: Minimizing Setups for Ordered Sets: A Linear Algebraic Approach
cites work: Q3686754
cites work: Optimal Linear Extensions by Interchanging Chains
cites work: Constructing greedy linear extensions by interchanging chains
cites work: Greedy linear extensions with constraints
cites work: On finding the jump number of a partial order by substitution decomposition
cites work: Q3676161
cites work: Jump number problem: The role of matroids
cites work: Minimizing bumps for posets of width two
full work available at URL: https://doi.org/10.1007/bf00337888
OpenAlex ID: W2033549036
description: scientific article; zbMATH DE number 4035885