Richard Kenyon, Daniel Kral, Charles Radin, Peter Winkler
A Variational Principle for Permutations
(3115K, pdf)
ABSTRACT. We define an entropy function for scaling limits of permutations, called permutons, and prove
that under appropriate circumstances, both the shape and number of large permutations with
given constraints are determined by maximizing entropy over permutons with
those constraints. We also describe a useful equivalent version of permutons
using a recursive construction.
This variational principle is used to study permutations with one or two
fixed pattern densities. In particular, we compute (sometimes directly, sometimes
numerically) the maximizing permutons with fixed density of $12$ patterns or
of fixed 123 density or both; with fixed 12 density and sum of 123 and 132 densities;
and finally with fixed 123 and 321 densities. In the last case we study a particular
phase transition.