Contents Online

# 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

#### 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.