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

Jacopo Borga (1) , Mathilde Bouvel (2, 1) , Valentin Feray (1) , Benedikt Stufler (3)

1 UZH - Universität Zürich [Zürich] = University of Zurich
2 MOCQUA - Designing the Future of Computational Models
3 Institut für Mathematik und Rechneranwendung [Munchen]

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

Mots clés: permutation patterns; local and scaling limits; Galton–Watson trees

Domaines: Combinatoire [math.CO]; Probabilités [math.PR]

Jacopo Borga, Mathilde Bouvel, Valentin Feray, Benedikt Stufler. A decorated tree approach to random permutations in substitution-closed classes. Electronic Journal of Probability, 2020, 25, ⟨10.1214/20-EJP469⟩. ⟨hal-02998759⟩