On the topology of the permutation pattern poset

DOI10.1016/J.JCTA.2015.02.009MaRDI QIDQ2347966zbMATH OpenOpenAlexFDO

Authors Einar Steingrímsson, Peter R. W. McNamara

Publication date 10 June 2015

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

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

zbMATH Keywords

disconnected subintervalsgeneralized subword orderlayered permutationsMöbius functionpattern posetshellable interval

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Partial orders, general (06A06)

Abstract: The set of all permutations, ordered by pattern containment, forms a poset. This paper presents the first explicit major results on the topology of intervals in this poset. We show that almost all (open) intervals in this poset have a disconnected subinterval and are thus not shellable. Nevertheless, there seem to be large classes of intervals that are shellable and thus have the homotopy type of a wedge of spheres. We prove this to be the case for all intervals of layered permutations that have no disconnected subintervals of rank 3 or more. We also characterize in a simple way those intervals of layered permutations that are disconnected. These results carry over to the poset of generalized subword order when the ordering on the underlying alphabet is a rooted forest. We conjecture that the same applies to intervals of separable permutations, that is, that such an interval is shellable if and only if it has no disconnected subinterval of rank 3 or more. We also present a simplified version of the recursive formula for the M"obius function of decomposable permutations given by Burstein et al.

Recommendations

• scientific article; zbMATH DE number 6928875
• On the Möbius function and topology of general pattern posets
• scientific article; zbMATH DE number 5186439
• A topological framework for signed permutations
• scientific article; zbMATH DE number 29539
• Topology of posets with special partial matchings
• Topology of posets with special partial matchings
• On permutation polytopes
• The topology of restricted partition posets
• The topology of restricted partition posets

Cites work

• A generalization of the Chebyshev polynomials and nonrooted posets
• A user's guide to discrete Morse theory
• Ascending sequences in permutations
• Bruhat order of Coxeter groups and shellability
• Counting fixed-length permutation patterns
• Criterion for smoothness of Schubert varieties in Sl(n)/B
• Discrete Morse functions from lexicographic orders
• Discrete Morse theory and the consecutive pattern poset
• Excluded permutation matrices and the Stanley-Wilf conjecture
• scientific article; zbMATH DE number 6016068 (Why is no real title available?)
• scientific article; zbMATH DE number 4158687 (Why is no real title available?)
• scientific article; zbMATH DE number 1033382 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• scientific article; zbMATH DE number 970688 (Why is no real title available?)
• Morse theory for cell complexes
• Obstructions to shellability
• On Lexicographically Shellable Posets
• On the Möbius function of permutations with one descent
• Pattern matching for permutations
• Patterns in permutations and words.
• Poset topology: tools and applications
• Restricted permutations
• Shellability of interval orders
• Shellable and Cohen-Macaulay Partially Ordered Sets
• Some open problems on permutation patterns
• 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 consecutive pattern poset
• The Möbius function of the permutation pattern poset
• The patterns of permutations
• The structure of the consecutive pattern poset

Cited in

(19)

• Topological equivalents to n-permutability
• Vincular pattern posets and the Möbius function of the quasi-consecutive pattern poset
• The Möbius function of permutations with an indecomposable lower bound
• On the Möbius function and topology of general pattern posets
• Pattern posets
• On the growth of the Möbius function of permutations
• Interval posets of permutations
• The poset of mesh patterns
• On the poset of non-attacking King permutations
• The poset of graphs ordered by induced containment
• A formula for the Möbius function of the permutation poset based on a topological decomposition
• scientific article; zbMATH DE number 5186439 (Why is no real title available?)
• scientific article; zbMATH DE number 6928875 (Why is no real title available?)
• The structure of the consecutive pattern poset
• Intervals of permutations with a fixed number of descents are shellable
• On intervals of the consecutive pattern poset
• 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
• Interview with Einar Steingrímsson

This page was built for publication: On the topology of the permutation pattern poset

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