The Möbius function of the poset of permutations

排列是可以相对于给定的总顺序成对比较的对象列表，因此它们总是可以用整数表示，其中顺序是通常的大小顺序。排列中的模式P是该排列中的子序列，其元素以与P中的元素相同的大小顺序出现。例如，641523中的字母452形成模式231的出现。近几十年来，关于排列的各种特性的研究在模式遏制方面取得了巨大的发展，并与离散数学的其他分支，甚至与物理学、生物学和理论计算机科学建立了无数的联系，其中理论计算机科学与该领域的现代体现有着密切的联系。长期以来，这一领域的焦点主要集中在枚举结果上，但对所有有限排列的偏序集（部分有序集）的结构性质的研究，在过去十年左右的时间里得到了大力发展。到目前为止，这些主要是关于这个偏序集的序理想，即元素的向下闭类，类似于图的小闭类。这个偏序集是所有排列模式研究的基本对象，因为它包含了关于排列中包含和避免模式的所有信息。关于任意组合定义的偏序集的一个不可避免的问题是关于其区间的Möbius函数，即包含给定的排列a和包含另一个给定的排列b的置换集合。Möbius函数可能是组合定义的偏序集最重要的不变量。除了确定这个偏序集的Möbius函数的内在兴趣，以及它可能对其拓扑研究产生的影响之外，已经有结果表明，Möbius函数在某些情况下与一个排列作为另一个排列的模式出现的次数密切相关，这是排列模式领域的中心问题之一。此外，这种联系是本建议的核心，因此我们期望这里的成功对排列模式的枚举研究产生影响。对置换偏序集Möbius函数的研究虽然只有几年的时间，但已经很清楚，这个偏序集的结构非常丰富和复杂，这反映了该领域列举性问题的情况。由于这种复杂性，似乎不太可能有一个有效的、完全通用的Möbius函数公式，但这当然是有趣的数学结构经常出现的情况。鉴于已经取得的进展，这不应被视为令人沮丧，而应被视为具有挑战性的邀请。在为一类区间确定Möbius函数的所有情况下，解决方案都有一个共同的线程。这些是所谓的正常嵌入，一个排列在另一个中的特殊出现，它们非常相似，但在不同的情况下仍然不同，并且它们在每个情况中的数量本质上等于对应间隔的Möbius函数。有趣的是，经验测试表明，这些正常嵌入定义的另一种变体给出了类似的结果，即，在“不合理”的大比例情况下，这些嵌入的数量等于Möbius函数，远远超出了我们现在对这一现象的理解范围。这就是我们想要理解的，因为它几乎肯定会导致对该偏序集的Möbius函数的研究取得实质性进展，对其一般结构产生更系统的结果，并为进一步的进展提供工具。

Permutations are lists of objects that can be compared pairwise with respect to a given total order, and they can thus always be represented by integers, where the order is the usual order of size. A pattern P in a permutation is a subsequence in the permutation whose elements appear in the same order of size as those in P. For example, the letters 452 in 641523 form an occurrence of the pattern 231. In recent decades research on various properties of permutations with respect to pattern containment has seen enormous growth, and established a myriad connections to other branches of discrete mathematics and even to physics, biology and theoretical computer science, the last of which has been strongly connected to the field in its modern incarnation. The focus in this field was for a long time mainly on enumerative results, but studies of structural properties of the poset (partially ordered set) of all finite permutations, ordered by pattern containment, have been growing strong in the last decade or so. These have so far mostly concerned order ideals in this poset, that is, downward closed classes of elements, analogous to minor closed classes of graphs. This poset is the fundamental object in all studies of permutation patterns, since it encompasses all information about containment and avoidance of patterns in permutations.An inevitable question about any combinatorially defined poset regards the Möbius function of its intervals, that is, sets of permutations containing a given permutation A and contained in another given permutation B. The Möbius function is probably the single most important invariant of a combinatorially defined poset. In addition to the intrinsic interest of determining the Möbius function for this poset, and the likely effect it will have on studies of its topology, there are already results showing that the Möbius function is in some cases closely connected to the number of occurrences of one permutation as a pattern in another, one of the central problems in the area of permutation patterns. Moreover, such a connection is at the core of this proposal, so we expect success here to have an impact on the enumerative studies of permutation patterns.The study of the Möbius function of the permutation poset has only been going on for a few years, but it is already clear that this poset has a very rich and complicated structure, which reflects the situation with the enumerative problems in the area. Because of this complexity it seems unlikely there will ever be an effective and completely general formula for the Möbius function, but that is of course often the case with interesting mathematical structures. In light of the progress nevertheless made already, this should not be seen as discouraging, but as a challenging invitation. In all cases where the Möbius function has been determined for a class of intervals there is a common thread to the solutions. These are the so called normal embeddings, special occurrences of a permutation in another, which are very similar, but still different between the cases, and whose number in each of these cases is essentially equal to the Möbius function of the corresponding intervals. Intriguingly, empirical tests show that yet another variation on the definition of these normal embeddings gives analogous results, that is, that the number of these embeddings equals the Möbius function, in an ``unreasonably'' large proportion of cases, far beyond the realm of where we now understand this phenomenon. This is what we want to understand, since it will almost definitely lead to substantial progress in the research on the Möbius function of this poset, to more systematic results on its general structure, and to tools for further progress.