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

Producción científica: Article › revisión exhaustiva

5 Citas (Scopus)

Resumen

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.

Idioma original	English
Páginas (desde-hasta)	1-8
Número de páginas	8
Publicación	Order
Volumen	2
N.º	1
DOI	https://doi.org/10.1007/BF00337919
Estado	Published - mar 1985

ASJC Scopus subject areas

Algebra and Number Theory
Geometry and Topology
Computational Theory and Mathematics

Acceder al documento

10.1007/BF00337919

Otros archivos y enlaces

Citar esto

@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 - https://www.scopus.com/pages/publications/30244470235

UR - https://www.scopus.com/pages/publications/30244470235#tab=citedBy

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

Resumen

ASJC Scopus subject areas

Acceder al documento

Otros archivos y enlaces

Huella

Citar esto