权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

The Möbius function of the poset of permutations

排列偏序集的莫比乌斯函数

基本信息

批准号：
EP/M027147/1
负责人：
Einar Steingrimsson
金额：
$ 36.31万
依托单位：
University of Strathclyde
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2015
资助国家：
英国
起止时间：
2015 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FM027147%2F1
关键词：
bius function poset permutations

项目摘要

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.

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