PC Seminar: Random Permutations: of Cycles and Letters

Abstract: A permutation can be seen as either a union of cycles or a sequence of letters. Although these two points of view are equivalent, switching between them is not so simple. For example, suppose you are given the cycle counts of a typical permutation; what can you hope to deduce about its number of inversions?

The setting we will adopt is as follows: sample a uniformly random permutation with a given sequence of cycle counts, and study some of its ``word statistics'' (e.g., the number of inversions, the longest increasing subsequence, the number of left-to-right maxima, ...). A series of results in the literature seem to indicate some kind of universality phenomenon for such statistics: the asymptotic behavior depends merely on the number of fixed points (for the first-order asymptotics) and on the number of 2-cycles (for the second-order asymptotics).

In this talk, we will present a ``geometric'' approach to constructing uniform permutations in given conjugacy classes. This construction relies on a point process on $[0,1]^2$ which boasts very appealing features, such as weak dependency and local uniformity. It can be used to analyze an array of ``word statistics'' for which we establish asymptotic universality (although, several questions remain open).

This is a seminar in our seminar series on Probability and Combinatorics (PC).