A decorated tree approach to random permutations in substitution-closed classes

Abstract

We establish a novel bijective encoding that represents permutations as forests of decorated (or enriched) trees. This allows us to prove local convergence of uniform random permutations from substitution-closed classes satisfying a criticality constraint. It also enables us to reprove and strengthen permuton limits for these classes in a new way, that uses a semi-local version of Aldous' skeleton decomposition for size-constrained Galton--Watson trees.

arXiv commentNew version including referee's corrections, accepted for publication in Electronic Journal of Probability

References in corpus (2)

• Invariance principles for Galton-Watson trees conditioned on the number of leaves
• Fixed points of 321-avoiding permutations

Cited by in corpus (7)

• Local convergence for permutations and local limits for uniform $\rho$-avoiding permutations with $|\rho |=3$
• Square permutations are typically rectangular
• Almost square permutations are typically square
• Scaling and local limits of Baxter permutations and bipolar orientations through coalescent-walk processes
• Asymptotic normality of consecutive patterns in permutations encoded by generating trees with one-dimensional labels
• The skew Brownian permuton: a new universality class for random constrained permutations
• Bounded affine permutations II. Avoidance of decreasing patterns