Limits of permutations
Polygon Iterations »


Limits of permutations
Submitted by the Institute for Computational and Experimental Research in Mathematics (ICERM)

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 [n]= {1, 2,...,n} there are about inversions, that is, pairs i for which π(j) <π(i). Suppose we are interested in studying permutations for which the number of inversions is exceptionally large or small, for example for some other α ∈ [0, 1]. What can one say about the structure and properties of such a permutation? For example, typically how many double inversions (triples i for which π(k) <π(j) <π(i)) might one expect?

Figure 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-n limit. What we are actually drawing is called a permuton: a probability measure on [0, 1]2 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 [n = 300] and 3/4 fraction of inversions is shown in Figure 2.

Figure 1

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

Generally a pattern in a permutation is an order-sequence imposed on a finite subset of [n]; 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 k in a permutation σ on [n] is the number of occurrences of the pattern π, divided by .

If we fix the densities d1,d2... of a few specific patterns, such as 12 and 123, the set of all permutations in Sn 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 3/4 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 Sn with given constraints is generally of the order n! exp(sn), the (negative) 'entropy' , maximizing entropy allows one to find the permuton. That is, one can define an entropy function H on the space Γ of permutons and the desired permuton is obtained by maximizing H over all permutons satisfying the given pattern constraints

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.