Universal limits of substitution-closed permutation classes (Q2216743)

This paper is about limiting objects of permutations whose building blocks are the so-called simple permutations: these are the permutations of the set \(\{1,\ldots, n\}\) that do not map an interval in another interval. The paper utilises a decomposition of a permutation into simple permutations under a certain set of rules. A key observation that facilitates the analysis is that this decomposition can be represented by a tree. The main result of this paper is about the limiting object of a random permutation that is sampled uniformly among all permutations that are generated by simple permutation of a given class. Under a certain condition on the generating function (and its radius of convergence) of this class, the authors show that the associated permuton of such a random permutation converges weakly (as a measure on \([0,1]^2\)) to the so-called biased Brownian permuton, which is introduced in the paper. It is characterised by specific frequencies of permutations of any fixed length \(\geq 2\). This notion is a generalisation of the unbiased Brownian permuton which was introduced by (a subset of) the authors in earlier work.