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

• 成果类型: Article
• 署名作者: Borga, Jacopo
• 署名单位: University of Zurich
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-019-00922-4
• 发表日期: 2020
• 页码: 449-531
• 关键词: galton-watson trees; pattern; excursion

摘要

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 rho-avoiding permutations, for vertical bar rho vertical bar = 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.