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.

This is basic research in a field of discrete mathematics with strong connections to theoretical computer science. Since the project is highly theoretical in nature its immediate impact is most likely to be in inspiring other researchers, and in initiating new directions in research. Given that the research proposed here is just taking off, and that the PI has been at the forefront of its recent development, we expect this work to have significant impact on the research community.

In the longer term, the research proposed here may benefit researchers in other areas, such as computer science and biology, and even physics. Patterns research has roots in theoretical computer science, and parts of pattern research straddle the border between discrete mathematics and computer science.

Patterns have played a role in genomics, especially in genome sorting, where many problems deal with likely rearrangements of genomes, both within species and when comparing species with a common ancestor. To boost collaboration between these two fields, a week long seminar at Dagstuhl will take place in February of 2016, entitled Pattern avoidance and genome sorting. I am one of the organisers of this seminar.

Patterns and closely related combinatorics have also appeared in physics, such as in the study of the Partially Asymmetric Exclusion Process and of so called Web Worlds of quantum chromodynamics.

As is usually the case with basic research, predicting the long term impact of this project is not easy.