The Möbius function of the poset of 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.