On the size of jump-critical ordered sets

DOI10.1007/BF00396268MaRDI QIDQ802585zbMATH OpenOpenAlexWikidataFDO

Authors Mohamed H. El-Zahar, James H. Schmerl

Publication date 1984

Published in Order (Search for Journal in Brave)

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

zbMATH Keywords

finite posetjump-critical ordered setlinear extensionsnumber of jumps

Mathematics Subject Classification ID

Combinatorial inequalities (05A20) Partial orders, general (06A06) Analysis of algorithms and problem complexity (68Q25)

Review text

The paper deals with a finite poset and its jump number which is the minimum number of jumps in its linear extensions. The result is that the size of a jump-critical ordered set with jump number m is at most \((m+1)!\).

Recommendations

• scientific article; zbMATH DE number 19350
• On the height and jump number of ordered sets
• scientific article; zbMATH DE number 4019120
• scientific article; zbMATH DE number 1558370
• On minimizing jumps for ordered sets
• On the Jump Number of Lexicographic Sums of Ordered Sets
• Ordered sets with small width and large jump number
• scientific article; zbMATH DE number 4089612
• On jump-critical posets with jump-number equal to width
• The jump number of Z-free ordered sets

Cites work

• A decomposition theorem for partially ordered sets
• Optimal Linear Extensions by Interchanging Chains
• The Jump Number of Dags and Posets: An Introduction

Cited in

(26)

• Jump number problem: The role of matroids
• Greedy linear extensions to minimize jumps
• Ordered sets with small width and large jump number
• Minimizing bumps in linear extensions of ordered sets
• NP-completeness results concerning greedy and super greedy linear extensions
• Greedy posets for the bump-minimizing problem
• Jump number and width
• Substitution and atomic extension on greedy posets
• The jump number of Z-free ordered sets
• On the poset of all posets on n elements
• On jump-critical posets with jump-number equal to width
• An improved algorithm for the jump number problem
• FPT Suspects and Tough Customers: Open Problems of Downey and Fellows
• scientific article; zbMATH DE number 4019120 (Why is no real title available?)
• On Posets of Page Number 2
• Examples of Jump-Critical Ordered Sets
• scientific article; zbMATH DE number 4089612 (Why is no real title available?)
• Jumps of Hemimaximal Sets
• On the Jump Number of Lexicographic Sums of Ordered Sets
• scientific article; zbMATH DE number 1558370 (Why is no real title available?)
• On the height and jump number of ordered sets
• Recent Results on the Size of Critical Sets
• scientific article; zbMATH DE number 2217189 (Why is no real title available?)
• The jump number of suborders of the power set order
• Well-quasi-ordering and Embeddability of Relational Structures
• The jump number and the lattice of maximal antichains

This page was built for publication: On the size of jump-critical ordered sets

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