Polygon Iterations » |

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

In a well-shuﬄed 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

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-deﬁned 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.

Generally a *pattern* in a permutation is an order-sequence imposed on a ﬁnite 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 ﬁx the densities *d _{1},d_{2}*... of a few speciﬁc patterns, such as 12 and 123, the set of all permutations in

How do we ﬁnd 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 *S _{n}* with given constraints
is generally of the order

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.