The Möbius Function of Generalized Subword Order

Peter R. W. McNamara; Bruce Eli Sagan

The Möbius Function of Generalized Subword Order

Peter R. W. McNamara, Bruce Eli Sagan

Bucknell University

Michigan State University

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

Abstract

Let P be a poset and let P ⁎ be the set of all finite length words over P . Generalized subword order is the partial order on P ⁎ obtained by letting u &les; w if and only if there is a subword u ′ of w having the same length as u such that each element of u is less than or equal to the corresponding element of u ′ in the partial order on P . Classical subword order arises when P is an antichain, while letting P be a chain gives an order on compositions. For any finite poset P , we give a simple formula for the Möbius function of P ⁎ in terms of the Möbius function of P . This permits us to rederive in an easy and uniform manner previous results of Björner, Sagan and Vatter, and Tomie. We are also able to determine the homotopy type of all intervals in P ⁎ for any finite P of rank at most 1.

Original language	American English
Journal	Default journal
Volume	229
State	Published - Mar 20 2012

Keywords

Chebyshev polynomial
Discrete Morse theory
homotopy type
minimal skipped interval
Möbius function
poset
subword order

Disciplines

Discrete Mathematics and Combinatorics
Geometry and Topology

Access to Document

http://www.facstaff.bucknell.edu/pm040/Papers/gso.pdf

Cite this

@article{c8b413a226f04e8d9ebe20e1572f412b,

title = "The M{\"o}bius Function of Generalized Subword Order",

abstract = " Let P be a poset and let P ⁎ be the set of all finite length words over P . Generalized subword order is the partial order on P ⁎ obtained by letting u \&les; w if and only if there is a subword u \′ of w having the same length as u such that each element of u is less than or equal to the corresponding element of u \′ in the partial order on P . Classical subword order arises when P is an antichain, while letting P be a chain gives an order on compositions. For any finite poset P , we give a simple formula for the M\öbius function of P ⁎ in terms of the M\öbius function of P . This permits us to rederive in an easy and uniform manner previous results of Bj\örner, Sagan and Vatter, and Tomie. We are also able to determine the homotopy type of all intervals in P ⁎ for any finite P of rank at most 1.",

keywords = "Chebyshev polynomial, Discrete Morse theory, homotopy type, minimal skipped interval, M{\"o}bius function, poset, subword order",

author = "McNamara, \{Peter R. W.\} and Sagan, \{Bruce Eli\}",

year = "2012",

month = mar,

day = "20",

language = "American English",

volume = "229",

journal = "Default journal",

}

TY - JOUR

T1 - The Möbius Function of Generalized Subword Order

AU - McNamara, Peter R. W.

AU - Sagan, Bruce Eli

PY - 2012/3/20

Y1 - 2012/3/20

N2 - Let P be a poset and let P ⁎ be the set of all finite length words over P . Generalized subword order is the partial order on P ⁎ obtained by letting u &les; w if and only if there is a subword u ′ of w having the same length as u such that each element of u is less than or equal to the corresponding element of u ′ in the partial order on P . Classical subword order arises when P is an antichain, while letting P be a chain gives an order on compositions. For any finite poset P , we give a simple formula for the Möbius function of P ⁎ in terms of the Möbius function of P . This permits us to rederive in an easy and uniform manner previous results of Björner, Sagan and Vatter, and Tomie. We are also able to determine the homotopy type of all intervals in P ⁎ for any finite P of rank at most 1.

AB - Let P be a poset and let P ⁎ be the set of all finite length words over P . Generalized subword order is the partial order on P ⁎ obtained by letting u &les; w if and only if there is a subword u ′ of w having the same length as u such that each element of u is less than or equal to the corresponding element of u ′ in the partial order on P . Classical subword order arises when P is an antichain, while letting P be a chain gives an order on compositions. For any finite poset P , we give a simple formula for the Möbius function of P ⁎ in terms of the Möbius function of P . This permits us to rederive in an easy and uniform manner previous results of Björner, Sagan and Vatter, and Tomie. We are also able to determine the homotopy type of all intervals in P ⁎ for any finite P of rank at most 1.

KW - Chebyshev polynomial

KW - Discrete Morse theory

KW - homotopy type

KW - minimal skipped interval

KW - Möbius function

KW - poset

KW - subword order

UR - https://digitalcommons.bucknell.edu/fac_journ/508

UR - http://www.facstaff.bucknell.edu/pm040/Papers/gso.pdf

M3 - Article

VL - 229

JO - Default journal

JF - Default journal

ER -

The Möbius Function of Generalized Subword Order

Abstract

Keywords

Disciplines

Access to Document

Other files and links

Cite this