Local convergence for random permutations: the case of uniform pattern-avoiding permutations

schedule le mercredi 27 juin 2018 de 17h00 à 18h00

Organisé par : C. Cosco, S. Coste, L. Marêché, P. Melotti, N. Meyer

Intervenant : Jacopo Borga (Institut für Mathematik, Universität Zürich)
Lieu : Jussieu, salle Paul Lévy, couloir 16-26 salle 113

Sujet : Local convergence for random permutations: the case of uniform pattern-avoiding permutations

Résumé :

For large combinatorial structures, two main notions of convergence can be defined: scaling limits and local limits. In particular for graphs, both notions are well-studied and well-understood. For permutations only a notion of scaling limits, called permutons, has been recently introduced. The convergence for permutons has also been characterized by frequencies of pattern occurrences.

We set up a new notion of local convergence for permutations and we prove a characterization in terms of proportions of consecutive pattern occurrences. We are also able to characterize random limiting objects introducing a “shift-invariant” property (corresponding to the notion of unimodularity for random graphs). We finally show two applications in the framework of random pattern-avoiding permutations, computing the local limits of uniform ρ-avoiding permutations for |ρ|=3. For this last result we use bijections between ρ-avoiding permutations and ordered rooted trees, a local limit result for Galton-Waltson trees, the Second moment method and singularity analysis.