Contents Online
Journal of Combinatorics
Volume 1 (2010)
Number 1
The Möbius function of the permutation pattern poset
Pages: 39 – 52
DOI: https://dx.doi.org/10.4310/JOC.2010.v1.n1.a3
Authors
Abstract
A permutation $\t$ contains another permutation $\s$ as a pattern if $\t$ has asubsequence whose elements are in the same order with respect to size as the elements in$\s$. This defines a partial order on the set of all permutations, and gives a gradedposet $\p$. We give a large class of pairs of permutations whose intervals in~$\p$ haveMöbius function $0$. Also, we give a solution to the problem when $\s$ occurs preciselyonce in $\t$, and $\s$ and $\t$ satisfy certain further conditions, in which case theMöbius function is shown to be either $-1$, $0$ or $1$. We conjecture that forintervals $[\s,\t]$ consisting of permutations avoiding the pattern 132, the magnitude ofthe Möbius function is bounded by the number of occurrences of $\s$ in $\t$. We alsoconjecture that the Möbius function of the interval $[1,\t]$ is $-1$, $0$ or $1$.
Keywords
Möbius function, permutation, permutation pattern, poset
2010 Mathematics Subject Classification
Primary 05A05. Secondary 06A07.
Published 1 January 2010