Inflations of geometric grid classes of permutations
Inflations of geometric grid classes of permutations
复制标题
排列的几何网格类的膨胀
DOI：
10.1007/s11856-014-1098-8
复制
发表时间：
2014
影响因子：
1
通讯作者：
Albert M
中科院分区：
文献类型：
--
作者：
Albert M
几何网格类和置换分解都被证明是理解置换类结构的基础。特别是，这是最近对增长率小于κ = 2.20557（一个特定的代数整数，在这个代数整数上，无限反链首次出现）的置换类进行分类的两个主要工具。使用语言和秩序理论的方法，我们证明了几何网格类的替代闭包是部分有序的，基于递归的，并且它们的所有子类都具有代数生成函数。我们继续表明，一个几何网格类的强理性类的通货膨胀是部分有序的，它的所有子类都有合理的生成函数。后一个事实使我们可以得出结论，每个增长率小于κ的置换类都有一个有理生成函数。这个界是紧的，因为存在具有非有理生成函数的增长率为κ的置换类。
Geometric grid classes and the substitution decomposition have both been shown to be fundamental in the understanding of the structure of permutation classes. In particular, these are the two main tools in the recent classification of permutation classes of growth rate less thanκ≈ 2.20557 (a specific algebraic integer at which infinite antichains first appear). Using language- and order-theoretic methods, we prove that the substitution closures of geometric grid classes are well partially ordered, finitely based, and that all their subclasses have algebraic generating functions. We go on to show that the inflation of a geometric grid class by a strongly rational class is well partially ordered, and that all its subclasses have rational generating functions. This latter fact allows us to conclude that every permutation class with growth rate less thanκhas a rational generating function. This bound is tight as there are permutation classes with growth rateκwhich have nonrational generating functions.
登录
查看更多内容
网格类和受限排列的斐波那契二分法
影响因子：
0.7
作者：
Sophie Huczynska;Vincent Vatter
通讯作者：
Vincent Vatter
影响因子：
1.1
作者：
M. Albert;M. Atkinson;N. Ruškuc
通讯作者：
N. Ruškuc
影响因子：
0.8
作者：
Albert, MH;Atkinson, MD
通讯作者：
Atkinson, MD
每个增长率高于 2.48188 的排列类别
影响因子：
0.8
作者：
Vincent Vatter
通讯作者：
Vincent Vatter
以完美的速度成长
DOI：
10.1017/s0963548309009699
发表时间：
2009
期刊：
Combinatorics, Probability and Computing
影响因子：
--
作者：
M. Albert;S. Linton
通讯作者：
S. Linton