Limits of Permutations

Institute: ICERM     October 2015

In a well-shuffled deck of cards, about half of the pairs of cards are out of order. Mathematically, we say that in a permutation of there are about inversions, that is, pairs for which .  Suppose we are interested in studying permutations for which the number of inversions is exceptionally large or small, for example for some other . What can one say about the structure and properties of such a permutation? For example, typically how many double inversions (triples for which ) might one expect?
limits-permutations-1

Figure 1: A permuton with density of inversions.

Figure 1 is an illustration of the shape of a large permutation with a fraction of inversions ( total inversions), in a large- limit. What we are actually drawing is called a permuton: a probability measure on with uniform marginals (well, we’re graphing its probability density function). How does a permuton describe a large permutation? A permuton is, in a well-defined sense, the limit of the scaled permutation matrices associated to larger and larger permutations. The permutation matrix associated to a permutation of and fraction of inversions is shown in Figure 2.
limits-permutations-2

Figure 2: A permutation matrix of a uniform random permutation with density of inversions.

Generally a pattern in a permutation is an order-sequence imposed on a finite subset of ; for instance, the permutation 34251 contains 5 copies of the pattern 231 (342, 341, 351, 451, and 251).  The density of a pattern of length in a permutation on is the number of occurrences of the pattern , divided by .

If we fix the densities of a few specific patterns, such as 12 and 123, the set of all permutations in with approximately those densities takes on a `bulk persona’, or limit shape. Most permutations in the set look alike; for example, their other pattern densities match.  Moreover, the limit shape, with
these constraints, varies smoothly (in fact analytically) except for an occasional singularity when a `phase boundary’ is crossed. This is why we can assert that
almost all permutations with density of inversions `look like’ Figure 1.

How do we find the permuton for a given set of densities? This can be realized with the recent derivation [Kenyon, Král’, Radin, Winkler: arxiv:1506.02340] of a variational principle. Starting from the fact that the number of permutations in with given constraints is generally of the order , the (negative) `entropy’ , maximizing entropy allows one to find the permuton. That is, one can define an entropy function on the space of permutons and the desired permuton is obtained by maximizing over all permutons satisfying the given pattern constraints :

limits-permutations-3

This gives a way to understand what a typical large, constrained permutation is like. If, as seems to be the usual case, there is a unique optimal permuton representing , we can, via integration over , obtain all other pattern densities of a typical large permutation with constraints . This opens up a world of phases and phase transitions in a new setting.

This variational principle was an outgrowth of the Spring 2015 program of the Institute for Computational and Experimental Research in Mathematics (ICERM), which hosted a series of activities on emergent phenomena and phase transitions.