A formula for the Möbius function of the permutation poset based on a topological decomposition
A formula for the Möbius function of the permutation poset based on a topological decomposition
复制标题
基于拓扑分解的置换偏序集莫比乌斯函数公式
DOI：
10.1016/j.aam.2017.06.002
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Jason P. Smith
中科院分区：
文献类型：
--
作者：
Jason P. Smith
我们提出了一个两项公式的莫比乌斯函数的间隔偏序集的所有排列，有序的模式包含。这个公式中的第一项是一个排列在另一个排列中的所谓正常出现的次数。我们对正规发生的定义与文献中关于这个偏序集和其他偏序集的莫比乌斯函数的几个变体中出现的定义相似，但比大多数定义简单。公式中的第二项很复杂，但我们推测它在很大一部分区间中等于零。我们提出了一些情况下，第二项为零和其他地方，它是非零的。从莫比乌斯函数的定义递归地计算它具有指数复杂性，而我们公式中第一项的计算是多项式的，指数部分被孤立于第二项，它似乎经常消失。我们还提出了一个结果的Möbius函数的偏序集连接的偏序集纤维化。
We present a two term formula for the Möbius function of intervals in the poset of all permutations, ordered by pattern containment. The first term in this formula is the number of so called normal occurrences of one permutation in another. Our definition of normal occurrences is similar to those that have appeared in several variations in the literature on the Möbius function of this and other posets, but simpler than most of them. The second term in the formula is complicated, but we conjecture that it equals zero for a significant proportion of intervals. We present some cases where the second term vanishes and others where it is nonzero. Computing the Möbius function recursively from its definition has exponential complexity, whereas the computation of the first term in our formula is polynomial and the exponential part is isolated to the second term, which seems to often vanish. We also present a result on the Möbius function of posets connected by a poset fibration.