On the growth of the Mobius function of permutations

Abstrakt

We study the values of the Mobius 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 vertical bar mu(1, pi)vertical bar in terms of vertical bar pi vertical bar, improving a previous quadratic bound by Smith. Our approach is based on a formula expressing the Mobil's function of an arbitrary permutation interval [alpha, beta] in terms of the number of embeddings of the elements of the interval into beta.

Klíčová slova

• Mobius function
• Permutation poset
• Permutation embedding