2413-balloon permutations and the growth of the Möbius function.
We show that the growth of the principal Möbius function on the permutation poset is exponential. This improves on previous work, which has shown that the growth is at least polynomial. We define a method of constructing a permutation from a smaller permutation which we call “ballooning”. We show that if β is a 2413-balloon, and π is the 2413-balloon of β, then μ[1, π] = 2μ[1, β]. This allows us to construct a sequence of permutations π_1, π_2, π_3 ... with lengths n, n+4, n + 8, ... such that μ[1, π_(i+1)] = 2μ [1, π_i], and this gives us exponential growth. Further, our construction method gives permutations that lie within a hereditary class with finitely many simple permutations. We also find an expression for the value of μ[1, π], where π is a 2413-balloon, with no restriction on the permutation being ballooned.
Brignall, R., Jelínek, V., Kynčl, J., Marchant, D.
Zeros of the Möbius function of permutations.
We show that if a permutation π contains two intervals of length 2, where one interval is an ascent and the other a descent, then the Möbius function μ[1, π] of the interval [1, π] is zero. As a consequence, we show that the proportion of permutations of length n with principal Möbius function equal to zero is asymptotically bounded below by (1−1/e)^2 ≥ 0.3995. This is the first result determining the value of μ[1, π] for an asymptotically positive proportion of permutations π. We also show that if a permutation φ can be expressed as a direct sum of the form α⊕1⊕β, then any permutation π containing an interval order-isomorphic to φ has μ[1, π] = 0; we deduce this from a more general result showing that μ[σ, π] = 0 whenever π contains an interval of a certain form. Finally, we show that if a permutation π contains intervals isomorphic to certain pairs of permutations, or to certain permutations of length six, then μ[1, π] = 0.
Brignall, R., and Marchant, D.
The Möbius function of permutations with an indecomposable lower bound.
, 341(5):1380-1391, 201
We show that the Möbius function of an interval in a permutation poset where the lower bound is sum (resp. skew) indecomposable depends solely on the sum (resp. skew) indecomposable permutations contained in the upper bound, and that this can simplify the calculation of the Möbius sum. For increasing oscillations, we give a recursion for the Möbius sum which only involves evaluating simple inequalities.