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

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.

Slides (PDF)


Dartmouth College in Hanover (USA, New Hampshire), Permutation Patterns 2018.


Laboratoire de Probabilités, Statistique et Modélisation de Paris (France), Groupe de travail des thésards du LPSM.


Universität Zürich (Switzerland), Discrete mathematics seminar.


Università degli Studi di Padova (Italy), Probability seminar.

Leave a Comment

Your email address will not be published.