Local convergence for permutations and local limits for uniform ρ-avoiding permutations with |ρ|=3

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 also characterize random limiting objects for this new topology introducing a notion of “shift-invariant” property (corresponding to the notion of unimodularity for random graphs).

We then study two models in the framework of random pattern-avoiding permutations. We compute the local limits of uniform ρ-avoiding permutations for |ρ| = 3 when the size tends to infinity.  The core part of the argument is the description of the asymptotics of the number of consecutive occurrences of any given pattern. For this result we use bijections between ρ-avoiding permutations and ordered rooted trees, local limit results for Galton–Watson trees, the Second moment method and singularity analysis.

arXiv(PDF)

five-page abstract for Permutation Patterns 2018

A poster for AEC 2018

 

On the top of the picture we have a uniform 321-avoiding permutation of length 94: on the top-left-hand side we can see the diagram of the whole permutation (global behaviour) and on the top-right-hand side the corresponding local behaviour around the red dot (chosen uniformly at random) in a vertical strip of size 21. On the bottom of the picture the same gobal and local behavior for a uniform 231-avoiding permutation of length 94.