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)

09/07/2018

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

27/06/2018

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

19/03/2018

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

20/02/2018

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

Leave a Comment

Your email address will not be published.