Journal of the European Mathematical Society


List online-first JEMS articles | JEMS summary
Published online first: 2020-08-04
DOI: 10.4171/JEMS/993

Universal limits of substitution-closed permutation classes

Frédérique Bassino[1], Mathilde Bouvel[2], Valentin Féray[3], Lucas Gerin[4], Mickaël Maazoun[5] and Adeline Pierrot[6]

(1) Université Paris 13, Sorbonne Paris Cité, Villetaneuse, France
(2) Universität Zürich, Switzerland
(3) Universität Zürich, Switzerland
(4) Ecole Polytechnique, Palaiseau, France
(5) École Normale Supérieure de Lyon, France
(6) Université Paris-Sud, Orsay, France

We consider uniform random permutations in proper substitution-closed classes and study their limiting behavior in the sense of permutons.

The limit depends on the generating series of the simple permutations in the class. Under a mild sufficient condition, the limit is an elementary one-parameter deformation of the limit of uniform separable permutations, previously identified as the Brownian separable permuton. This limiting object is therefore in some sense universal. We identify two other regimes with different limiting objects. The first one is degenerate; the second one is nontrivial and related to stable trees.

These results are obtained thanks to a characterization of the convergence of random permutons through the convergence of their expected pattern densities. The limit of expected pattern densities is then computed by using the substitution tree encoding of permutations and performing singularity analysis on the tree series.

Keywords: Permutation patterns, permutons

Bassino Frédérique, Bouvel Mathilde, Féray Valentin, Gerin Lucas, Maazoun Mickaël, Pierrot Adeline: Universal limits of substitution-closed permutation classes. J. Eur. Math. Soc. Electronically published on August 4, 2020. doi: 10.4171/JEMS/993 (to appear in print)