arXiv Analytics

Sign in

arXiv:1809.05774 [math.CO]AbstractReferencesReviewsResources

On the growth of the Möbius function of permutations

Vít Jelínek, Ida Kantor, Jan Kynčl, Martin Tancer

Published 2018-09-15Version 1

We study the values of the M\"obius 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\"obius function of an arbitrary permutation interval $[\alpha,\beta]$ in terms of the number of embeddings of the elements of the interval into $\beta$.

Comments: 34 pages, 4 figures
Categories: math.CO
Subjects: 05A05
Related articles: Most relevant | Search more
arXiv:1609.06646 [math.CO] (Published 2016-09-21)
The local $h$-polynomial of the edgewise subdivision of the simplex
arXiv:math/0507485 [math.CO] (Published 2005-07-22)
The Möbius function of the composition poset
arXiv:1306.5926 [math.CO] (Published 2013-06-25, updated 2014-04-02)
On the Möbius Function of Permutations With One Descent