Combinatorics Seminar

When: Sunday, November 15, 10am Where: Schreiber 309 Speaker: Richard Kenyon, Brown University Title: A variational principle for permutations

Abstract:

We study scaling limits of large permutations ("permutons"), constrained by fixing certain of pattern densities, for example, the density of inversions or `123' patterns. We show that the limit shapes are determined by maximizing entropy over permutons with those constraints. In particular, we compute (exactly or numerically) the limit shapes with fixed 12 density, with fixed 12 and 123 densities, with fixed 12 density and the sum of 123 and 213 densities. In some cases one can find interesting phase transitions as one varies the densities. To obtain our results, we also provide a description of permutons using a dynamic construction.

This is joint work with Daniel Kráľ, Charles Radin and Pete Winkler.