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 language | English |
---|---|
Pages (from-to) | 1-8 |
Number of pages | 8 |
Journal | Order |
Volume | 2 |
Issue number | 1 |
DOIs | |
State | Published - 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