论文标题
在模式遏制顺序下置换的Möbius函数
On the Möbius function of permutations under the pattern containment order
论文作者
论文摘要
我们在模式遏制顺序下的置换率上研究了Möbius函数的几个方面，即$μ[σ，π] $。 首先，我们考虑POSET的下限是不可分解的情况。我们表明，只需考虑上限中包含的不可分解的排列，就可以计算$μ[σ，π] $。我们将其应用于上限增加振荡的情况，并提供一种计算Möbius函数值的方法，该方法仅涉及评估简单的不平等现象。 然后，我们考虑一个间隔的条件，该条件确保Möbius函数的值为零。特别是，我们表明，如果置换$π$包含两个长度2的间隔，它们彼此不是订单形成的，则$μ[1，π] = 0 $。这使我们可以证明，长度$ n $与主莫比乌斯函数等于零的置换的比例在下面渐近地限制在$（1-1/e）^2 \ ge 0.3995 $。这是确定$μ[1，π] $的值的第一个结果，对于排列的渐近正比例$π$。 此后，我们使用“ 2413-Balloon”置换量来表明主要的Möbius函数在排列poset上的生长是指数的。这改善了先前的工作，这表明生长至少是多项式。 然后，我们概括了2413-阵容的排列，并找到了这些概括的主要möbius函数值的递归。
We study several aspects of the Möbius function, $μ[σ,π]$, 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 $μ[σ,π]$ 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öbius function that only involves evaluating simple inequalities. We then consider conditions on an interval which guarantee that the value of the Möbius function is zero. In particular, we show that if a permutation $π$ contains two intervals of length 2, which are not order-isomorphic to one another, then $μ[1,π] = 0$. This allows us to prove 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 \ge 0.3995$. This is the first result determining the value of $μ[1,π]$ for an asymptotically positive proportion of permutations $π$. Following this, we use ''2413-balloon'' permutations to 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 then generalise 2413-balloon permutations, and find a recursion for the value of the principal Möbius function of these generalisations.
