Intervals of permutations with a fixed number of descents are shellable

DOI10.1016/J.DISC.2015.08.004zbMATH Open1322.05004arXiv1405.2560OpenAlexW1939113383MaRDI QIDQ501038FDOQ501038

Authors: Jason P. Smith 

Publication date: 8 October 2015

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Combinatorics and commutative algebra.
• Shellable and Cohen-Macaulay Partially Ordered Sets
• Poset topology: tools and applications
• Combinatorial algebraic topology
• Title not available (Why is that?)
• The Möbius function of a composition poset
• On the Möbius function of permutations with one descent
• 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
• Restricted growth functions and incidence relations of the lattice of partitions of an n-set
• On the topology of the permutation pattern poset

Cited In (12)

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

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)