Intervals of permutations with a fixed number of descents are shellable

DOI10.1016/J.DISC.2015.08.004MaRDI QIDQ501038zbMATH OpenOpenAlexFDO

Authors Jason P. Smith

Publication date 8 October 2015

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1405.2560

zbMATH Keywords

shellabilitypermutation posetMöbius function

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Graph theory (including graph drawing) in computer science (68R10) Combinatorics on words (68R15)

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"obius function of these intervals. We present an alternative proof for a result on the M"obius function of intervals $[1,pi]$ such that $pi$ has exactly one descent. We prove that if $pi$ has exactly one descent and avoids 456123 and 356124, then the intervals $[1,pi]$ have no nontrivial disconnected subintervals; we conjecture that these intervals are shellable.

Recommendations

• On the topology of the permutation pattern poset
• scientific article; zbMATH DE number 6928875
• On the Möbius function of permutations with one descent
• On intervals of the consecutive pattern poset
• The Möbius function of the permutation pattern poset

Cites work

• scientific article; zbMATH DE number 6016068 (Why is no real title available?)
• scientific article; zbMATH DE number 4158687 (Why is no real title available?)
• Combinatorial algebraic topology
• Combinatorics and commutative algebra.
• On the Möbius function of permutations with one descent
• On the topology of the permutation pattern poset
• Poset topology: tools and applications
• Restricted growth functions and incidence relations of the lattice of partitions of an n-set
• Shellable and Cohen-Macaulay Partially Ordered Sets
• The Möbius function of a composition poset
• The Möbius function of generalized subword order
• The Möbius function of separable and decomposable permutations
• The Möbius function of the permutation pattern poset

Cited in

(12)

• A formula for the Möbius function of the permutation poset based on a topological decomposition
• The poset of mesh patterns
• On the Möbius function of permutations with one descent
• The poset of graphs ordered by induced containment
• Zeros of the Möbius function of permutations
• Pattern posets
• On the Möbius function and topology of general pattern posets
• On intervals of the consecutive pattern poset
• On the growth of the Möbius function of permutations
• The Möbius function of permutations with an indecomposable lower bound
• The history of the Gothenburg--Reykjavík--Strathclyde combinatorics group
• A formula for the Möbius function of the permutation poset based on a topological decomposition

Describes a project that uses

Uses Software

• GAP

This page was built for publication: Intervals of permutations with a fixed number of descents are shellable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q501038)