On the growth of the Möbius function of permutations

Abstract

We study the values of the Möbius function $\mu$ of intervals in the containment poset of permutations. We construct a sequence of permutations ${\pi }_n$ of size $2n-2$ for which $\mu (1,{\pi }_n)$ is given by a polynomial in $n$ of degree 7. This construction provides the fastest known growth of $|\mu (1,\pi )|$ in terms of $|\pi |$, improving a previous quadratic bound by Smith. Our approach is based on a formula expressing the Möbius function of an arbitrary permutation interval $[\alpha ,\beta ]$ in terms of the number of embeddings of the elements of the interval into $\beta$.

36 pages, 4 figures. Minor updates based on JCTA referees' comments; added reference to arXiv:1812.05064