On the M\"{o}bius function of permutations under the pattern containment order

DOI10.21954/OU.RO.00011477MaRDI QIDQ6356983zbMATH OpenFDO

Authors David Marchant

Publication date 26 December 2020

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Abstract: We study several aspects of the M"{o}bius function, $mu[sigma,pi]$, on the poset of permutations under the pattern containment order. First, we consider cases where the lower bound of the poset is indecomposable. We show that $mu[sigma,pi]$ can be computed by considering just the indecomposable permutations contained in the upper bound. We apply this to the case where the upper bound is an increasing oscillation, and give a method for computing the value of the M"{o}bius function that only involves evaluating simple inequalities. We then consider conditions on an interval which guarantee that the value of the M"{o}bius function is zero. In particular, we show that if a permutation $pi$ contains two intervals of length 2, which are not order-isomorphic to one another, then $mu[1,pi]=0$. This allows us to prove that the proportion of permutations of length $n$ with principal M"{o}bius function equal to zero is asymptotically bounded below by $(1-1/e{)}^{2}ge0.3995$. This is the first result determining the value of $mu[1,pi]$ for an asymptotically positive proportion of permutations $pi$. Following this, we use 2413-balloon permutations to show that the growth of the principal M"{o}bius function on the permutation poset is exponential. This improves on previous work, which has shown that the growth is at least polynomial. We then generalise 2413-balloon permutations, and find a recursion for the value of the principal M"{o}bius function of these generalisations.

This page was built for publication: On the M\"{o}bius function of permutations under the pattern containment order

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6356983)