Journal of Combinatorics

Volume 1 (2010)

Number 1

The Möbius function of the permutation pattern poset

Pages: 39 – 52

DOI: http://dx.doi.org/10.4310/JOC.2010.v1.n1.a3

Authors

Einar Steingrímsson (The Mathematics Institute, School of Computer Science, Reykjavík University, Iceland)

Bridget Eileen Tenner (Department of Mathematical Sciences, DePaul University, Chicago, Illinois, U.S.A.)

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.

Full Text (PDF format)