15-46 Richard Kenyon, Daniel Kral, Charles Radin, Peter Winkler

A Variational Principle for Permutations (3115K, pdf) Jun 9, 15

Abstract , Paper (src), View paper (auto. generated pdf), Index of related papers

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.

Files: 15-46.src( 15-46.comments , 15-46.keywords , permutons11.pdf.mm )