Scaling limits of permutation classes with a finite specification: A dichotomy
Scaling limits of permutation classes with a finite specification: A dichotomy
复制标题
具有有限规范的排列类的缩放限制：二分法
DOI：
10.1016/j.aim.2022.108513
复制
发表时间：
2019
影响因子：
1.7
通讯作者：
A. Pierrot
中科院分区：
文献类型：
--
作者：
Frédérique Bassino;M. Bouvel;Valentin Féray;L. Gerin;M. Maazoun;A. Pierrot
我们考虑具有有限组合规范的替换分解类中的均匀随机排列。这些类包括（但不限于）具有有限数量的简单排列的所有排列类。我们的目标是研究它们在排列意义上的限制行为。该限制取决于限制于增长率最大的家族的规范结构。当强连接时，会出现两种情况。如果关联的方程组是线性的，则极限排列是确定性的 X 形。否则，极限排列是布朗可分离排列，它是一个随机对象，已经作为大多数替代封闭排列类的极限出现，其中可分离排列。此外，这些结果可以结合起来研究一些非强连接的情况。为了证明我们的结果，我们使用随机子排列的收敛性来表征随机排列的收敛性。关键步骤是通过替换树对具有诱导给定模式的标记元素的排列族进行组合研究，以及相应生成函数的奇异性分析。
We consider uniform random permutations in classes having a finite combinatorial specification for the substitution decomposition. These classes include (but are not limited to) all permutation classes with a finite number of simple permutations. Our goal is to study their limiting behavior in the sense of permutons.The limit depends on the structure of the specification restricted to families with the largest growth rate. When it is strongly connected, two cases occur. If the associated system of equations is linear, the limiting permuton is a deterministicX-shape. Otherwise, the limiting permuton is the Brownian separable permuton, a random object that already appeared as the limit of most substitution-closed permutation classes, among which the separable permutations. Moreover these results can be combined to study some non strongly connected cases.To prove our result, we use a characterization of the convergence of random permutons by the convergence of random subpermutations. Key steps are the combinatorial study, via substitution trees, of families of permutations with marked elements inducing a given pattern, and the singularity analysis of the corresponding generating functions.
有限强制图子和排列
DOI：
10.1016/j.jctb.2014.07.007
发表时间：
2015
期刊：
J. Comb. Theory, Ser. B
影响因子：
--
作者：
R. Glebov;A. Grzesik;T. Klimošová;D. Král’
通讯作者：
D. Král’