Intervals of permutations with a fixed number of descents are shellable

Jason P. Smith

Research output: Contribution to journalArticle

4 Citations (Scopus)

Abstract

The set of all permutations, ordered by pattern containment, is a poset. We present an order isomorphism from the poset of permutations with a fixed number of descents to a certain poset of words with subword order. We use this bijection to show that intervals of permutations with a fixed number of descents are shellable, and we present a formula for the Möbius function of these intervals. We present an alternative proof for a result on the Möbius function of intervals [1,π] such that π has exactly one descent. We prove that if π has exactly one descent and avoids 456123 and 356124, then the intervals [1,π] have no nontrivial disconnected subintervals; we conjecture that these intervals are shellable.
LanguageEnglish
Pages118–126
Number of pages9
JournalDiscrete Mathematics
Volume339
Issue number1
Early online date27 Aug 2015
DOIs
Publication statusPublished - 2015

Fingerprint

Descent
Permutation
Interval
Poset
Möbius Function
Subword
Bijection
Isomorphism
Alternatives

Keywords

  • permutation Poset
  • shellability
  • möbius function

Cite this

Smith, Jason P. / Intervals of permutations with a fixed number of descents are shellable. In: Discrete Mathematics. 2015 ; Vol. 339, No. 1. pp. 118–126.
@article{32c23bd4770a41478133a12a9f858031,
title = "Intervals of permutations with a fixed number of descents are shellable",
abstract = "The set of all permutations, ordered by pattern containment, is a poset. We present an order isomorphism from the poset of permutations with a fixed number of descents to a certain poset of words with subword order. We use this bijection to show that intervals of permutations with a fixed number of descents are shellable, and we present a formula for the M{\"o}bius function of these intervals. We present an alternative proof for a result on the M{\"o}bius function of intervals [1,π] such that π has exactly one descent. We prove that if π has exactly one descent and avoids 456123 and 356124, then the intervals [1,π] have no nontrivial disconnected subintervals; we conjecture that these intervals are shellable.",
keywords = "permutation Poset, shellability, m{\"o}bius function",
author = "Smith, {Jason P.}",
year = "2015",
doi = "10.1016/j.disc.2015.08.004",
language = "English",
volume = "339",
pages = "118–126",
journal = "Discrete Mathematics",
issn = "0012-365X",
number = "1",

}

Intervals of permutations with a fixed number of descents are shellable. / Smith, Jason P.

In: Discrete Mathematics, Vol. 339, No. 1, 2015, p. 118–126.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Intervals of permutations with a fixed number of descents are shellable

AU - Smith, Jason P.

PY - 2015

Y1 - 2015

N2 - The set of all permutations, ordered by pattern containment, is a poset. We present an order isomorphism from the poset of permutations with a fixed number of descents to a certain poset of words with subword order. We use this bijection to show that intervals of permutations with a fixed number of descents are shellable, and we present a formula for the Möbius function of these intervals. We present an alternative proof for a result on the Möbius function of intervals [1,π] such that π has exactly one descent. We prove that if π has exactly one descent and avoids 456123 and 356124, then the intervals [1,π] have no nontrivial disconnected subintervals; we conjecture that these intervals are shellable.

AB - The set of all permutations, ordered by pattern containment, is a poset. We present an order isomorphism from the poset of permutations with a fixed number of descents to a certain poset of words with subword order. We use this bijection to show that intervals of permutations with a fixed number of descents are shellable, and we present a formula for the Möbius function of these intervals. We present an alternative proof for a result on the Möbius function of intervals [1,π] such that π has exactly one descent. We prove that if π has exactly one descent and avoids 456123 and 356124, then the intervals [1,π] have no nontrivial disconnected subintervals; we conjecture that these intervals are shellable.

KW - permutation Poset

KW - shellability

KW - möbius function

UR - http://www.sciencedirect.com/science/journal/0012365X

U2 - 10.1016/j.disc.2015.08.004

DO - 10.1016/j.disc.2015.08.004

M3 - Article

VL - 339

SP - 118

EP - 126

JO - Discrete Mathematics

T2 - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 1

ER -