Scaling limits of permutation classes with a finite specification: a dichotomy (Q2155196)

This paper provides the limiting distribution of a random permutation on \(n\) elements (without loss of generality, on the set \(\{1,\ldots, n\}\)) sampled uniformly from a class of permutations which admit combinatorial specification. Roughly speaking, such a permutation can be written recursively in terms of substitutions with permutations from the same class, but with certain specifications (one of which is that the substituting permutation may be among the simple permutations in the class). In fact, the paper considers families of such classes allowing substitution from each one of them. This gives rise to a system of generating functions which describes the dependencies between the generating functions of these classes. An important notion that is associated with these generating functions is that of criticality. The sub-family of generating functions whose radius of convergence is minimum is are called critical (this term is also applied to the family itself whose generating function is critical). Now, system which describes the dependencies between these functions gives rise to a directed graph on these families of permutation, where an arrow is added from one family to another if the generating function of the latter depends on the generating function of the former. The paper assumes that the subgraph induced by the critical families is strongly connected. The two main results of the paper identify a dichotomy on the limiting object of such random permutations. One sub-class of them (that satisfies certain properties) converge in distribution to a (deterministic) X-shaped permuton. The other sub-class converge to the same so-called Brownian permuton. (In this context, the term ``convergence'' refers to the convergence of the associated measure on \([0,1]^2\) that is induced by a permutation.)