Greedy posets for the bump-minimizing problem

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 which is apparently much more difficult to handle. Comparing the definitions of bump and jump against the background of arbitrary posets in their astronomical variety, this may not seem too surprising upon consideration.

Recommendations

Cites work

Cited in

(11)

This page was built for publication: Greedy posets for the bump-minimizing problem

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