Jump number problem: The role of matroids

Mirosław Truszczyński

doi:10.1007/BF00337919

Jump number problem: The role of matroids

Mirosław Truszczyński

Computer Science

Research output: Contribution to journal › Article › peer-review

5 Scopus citations

Abstract

Let L=x₁x₂... x_n be a linear extension of a poset P. Each pair (x_i, x_i+1) such that x_i≮ x_i+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	https://doi.org/10.1007/BF00337919
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

Access to Document

10.1007/BF00337919

Cite this

@article{3442bc9df9bd49bf8c091789326ab30d,

title = "Jump number problem: The role of matroids",

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.",

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

author = "Miros{\l}aw Truszczy{\'n}ski",

year = "1985",

month = mar,

doi = "10.1007/BF00337919",

language = "English",

volume = "2",

pages = "1--8",

number = "1",

}

TY - JOUR

T1 - Jump number problem

T2 - The role of matroids

AU - Truszczyński, Mirosław

PY - 1985/3

Y1 - 1985/3

N2 - 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.

AB - 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.

KW - AMS (MOS) subject classification (1980): 06A10

KW - Jump number

KW - N-free poset

KW - Poset

KW - Rado-Edmonds theorem

KW - greedy algorithm

KW - linear extension

KW - matroid

UR - http://www.scopus.com/inward/record.url?scp=30244470235&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=30244470235&partnerID=8YFLogxK

U2 - 10.1007/BF00337919

DO - 10.1007/BF00337919

M3 - Article

AN - SCOPUS:30244470235

SN - 0167-8094

VL - 2

SP - 1

EP - 8

JO - Order

JF - Order

IS - 1

ER -

Jump number problem: The role of matroids

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this