Jump number problem: The role of matroids

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

Let L=x1x2... xn be a linear extension of a poset P. Each pair (xi, xi+1) such that xi≮ xi+1in P is called a jump of L. It is well known that for N-free posets a natural 'greedy' procedure constructing linear extensions yields a linear extension with a minimum number of jumps. We show that there is a matroid corresponding to any N-free poset and apply the Rado-Edmonds Theorem to obtain another proof of this result.

Original languageEnglish
Pages (from-to)1-8
Number of pages8
JournalOrder
Volume2
Issue number1
DOIs
StatePublished - Mar 1985

Keywords

  • AMS (MOS) subject classification (1980): 06A10
  • Jump number
  • N-free poset
  • Poset
  • Rado-Edmonds theorem
  • greedy algorithm
  • linear extension
  • matroid

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Geometry and Topology
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Jump number problem: The role of matroids'. Together they form a unique fingerprint.

Cite this