The Möbius function of the permutation pattern poset

DOI10.4310/JOC.2010.V1.N1.A3MaRDI QIDQ989228zbMATH OpenFDO

Authors Einar Steingrímsson, Bridget Eileen Tenner

Publication date 30 August 2010

Published in Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

permutationposetpermutation patternMöbius function

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorics of partially ordered sets (06A07) Combinatorics and topology in relation with holomorphic dynamical systems (37F20)

Abstract: A permutation au contains another permutation sigma as a pattern if au has a subsequence whose elements are in the same order with respect to size as the elements in sigma. This defines a partial order on the set of all permutations, and gives a graded poset P. We give a large class of pairs of permutations whose intervals in P have Mobius function 0. Also, we give a solution to the problem when sigma occurs precisely once in au, and sigma and au satisfy certain further conditions, in which case the Mobius function is shown to be either -1, 0 or 1. We conjecture that for intervals [sigma, au] consisting of permutations avoiding the pattern 132, the magnitude of the Mobius function is bounded by the number of occurrences of sigma in au. We also conjecture that the Mobius function of the interval [1, au] is -1, 0 or 1.

Recommendations

• The Möbius function of the consecutive pattern poset
• On the Möbius function of permutations with one descent
• 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
• scientific article; zbMATH DE number 6806830

Cited in

(23)

• A formula for the Möbius function of the permutation poset based on a topological decomposition
• The poset of mesh patterns
• Generalized Dold sequences on partially-ordered sets
• On the Möbius function of permutations with one descent
• The Möbius function of generalized subword order
• The Möbius function of the consecutive pattern poset
• The Möbius function of separable and decomposable permutations
• The poset of graphs ordered by induced containment
• Zeros of the Möbius function of permutations
• scientific article; zbMATH DE number 6806830 (Why is no real title available?)
• Permutation classes and polyomino classes with excluded submatrices
• The Möbius function of the \(P\)-partition lattice
• Some open problems on permutation patterns
• On the topology of the permutation pattern poset
• Intervals of permutations with a fixed number of descents are shellable
• Vincular pattern posets and the Möbius function of the quasi-consecutive pattern poset
• 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
• Interview with Einar Steingrímsson
• 2413-balloon permutations and the growth of the Möbius function
• A formula for the Möbius function of the permutation poset based on a topological decomposition

This page was built for publication: The Möbius function of the permutation pattern poset

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