Local convergence for permutations and local limits for uniform $$\rho $$ρ-avoiding permutations with $$|\rho |=3$$|ρ|=3
Local convergence for permutations and local limits for uniform $$\rho $$ρ-avoiding permutations with $$|\rho |=3$$|ρ|=3
复制标题
排列的局部收敛和均匀 $$ ho $$ρ 的局部极限 - 避免 $$| ho |=3$$|ρ|=3 的排列
DOI：
10.1007/s00440-019-00922-4
复制
发表时间：
2018
影响因子：
2
通讯作者：
J. Borga
中科院分区：
文献类型：
--
作者：
J. Borga
我们建立了置换的局部收敛的新概念，并证明了用连续模式出现的比例表示的一个表征。我们还描述了这种新拓扑的随机极限对象，引入了“平移不变”性质的概念（对应于随机图的单模性概念）。然后，我们在随机避模排列的框架下研究了两个模型。对于$$|\rho |=3,$$ |ρ|=3，当排列的大小趋于无穷大时，我们计算了一致$$\rho $$ ρ-避免排列的局部极限。该论证的核心部分是对任意给定模式连续出现次数的渐近性的描述。对于这个结果，我们使用了$$\rho $$ ρ-避免置换与有根有序树之间的双射、Galton-Watson树的局部极限结果、第二矩法和奇点分析。
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 $$|\rho |=3,$$|ρ|=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.