Local convergence for permutations and local limits for uniform $\rho$-avoiding permutations with $|\rho |=3$

Abstract

We set up a new notion of local convergence for permutations and we prove a characterization in terms of proportions of \emph{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 $\rho$-avoiding permutations, for $|\rho |=3,$ when the size of the permutations 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 $\rho$-avoiding permutations and rooted ordered trees, local limit results for Galton--Watson trees, the Second moment method and singularity analysis.

arXiv comment62 pages, 22 figures, new version including referee's corrections, accepted for publication in Probability Theory and Related Fields

References in corpus (9)

• Uniqueness and universality of the Brownian map
• Uniform Infinite Planar Triangulations
• Limit of normalized quadrangulations: The Brownian map
• Thermodynamic Limit for the Mallows Model on $S_n$
• Patterns in random permutations avoiding the pattern 132
• A decorated tree approach to random permutations in substitution-closed classes
• Convergence of graphs with intermediate density
• Square permutations are typically rectangular
• Fixed points of 321-avoiding permutations

Cited by in corpus (5)

• Square permutations are typically rectangular
• Almost square permutations are typically square
• Scaling and local limits of Baxter permutations and bipolar orientations through coalescent-walk processes
• Asymptotic normality of consecutive patterns in permutations encoded by generating trees with one-dimensional labels
• Quenched law of large numbers and quenched central limit theorem for multi-player leagues with ergodic strengths