Universal limits of substitution-closed permutation classes

Abstract

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.

73 pages, 17 figures

References in corpus (3)

• The enumeration of simple permutations
• Fixed points and cycle structure of random permutations
• The enumeration of permutations avoiding 2143 and 4231

Cited by in corpus (14)

• The feasible region for consecutive patterns of permutations is a cycle polytope
• Splitting groups with cubic Cayley graphs of connectivity two
• Triangulations of simplices with vanishing local h-polynomial
• On the Brownian separable permuton
• Almost square permutations are typically square
• Linear-sized independent sets in random cographs and increasing subsequences in separable permutations
• Scaling and local limits of Baxter permutations and bipolar orientations through coalescent-walk processes
• The skew Brownian permuton: a new universality class for random constrained permutations
• Random Permutations -- A geometric point of view
• Locally uniform random permutations with large increasing subsequences
• Binary search trees of permuton samples
• Record-biased permutations and their permuton limit
• Bounded affine permutations II. Avoidance of decreasing patterns
• On the asymptotic enumeration and limit shapes of monotone grid classes of permutations