Stack-sorting with consecutive-pattern-avoiding stacks
Stack-sorting with consecutive-pattern-avoiding stacks
复制标题
使用避免连续模式的堆栈进行堆栈排序
DOI：
10.1016/j.aam.2021.102192
复制
发表时间：
2021
影响因子：
1.1
通讯作者：
Zheng, Kai
中科院分区：
文献类型：
--
作者：
Defant, Colin;Zheng, Kai
我们引入了避免召唤模式的堆栈排序映射SC σ，它是West堆栈排序映射s的自然推广，也是Cerbai，Claesson和Ferrari最近引入的避免经典模式的堆栈排序映射s σ的自然类似物.我们刻画了模式σ，使得Sort（SC σ）是一个置换类，Sort（SC σ）是通过映射s <$SC σ可排序的置换的集合，并且我们枚举了集合Sort（SC σ），其中σ∈{123，132，321}。我们还从动力学的角度研究了映射SC σ，对所有σ∈ S3刻画了SC σ的周期点，并计算了max π∈ Sn| SC σ− 1（π）|对于所有的σ∈{132，213，231，312}。此外，我们还刻画了避免经典模式的堆栈排序映射s132的周期点，并证明了将Sn中的置换发送到周期点所需的s132的最大迭代次数为n-1。论文最后提出了许多有待解决的问题和建议。
We introduce consecutive-pattern-avoiding stack-sorting maps SC σ, which are natural generalizations of West's stack-sorting map s and natural analogues of the classical-pattern-avoiding stack-sorting maps s σ recently introduced by Cerbai, Claesson, and Ferrari. We characterize the patterns σ such that Sort (SC σ), the set of permutations that are sortable via the map s∘ SC σ, is a permutation class, and we enumerate the sets Sort (SC σ) for σ∈{123, 132, 321}. We also study the maps SC σ from a dynamical point of view, characterizing the periodic points of SC σ for all σ∈ S 3 and computing max π∈ S n| SC σ− 1 (π)| for all σ∈{132, 213, 231, 312}. In addition, we characterize the periodic points of the classical-pattern-avoiding stack-sorting map s 132, and we show that the maximum number of iterations of s 132 needed to send a permutation in S n to a periodic point is n− 1. The paper ends with numerous open problems and conjectures.
登录
查看更多内容
已排序和/或可排序排列
影响因子：
0.8
作者：
M. Bousquet
通讯作者：
M. Bousquet
格子路径和模式避免唯一排序的排列
影响因子：
0.7
作者：
H. Mularczyk
通讯作者：
H. Mularczyk
2N 个非共线点确定至少 2N 个方向
DOI：
--
发表时间：
1982
期刊：
Journal of Combinatorial Theory
影响因子：
--
作者：
P. Ungar
通讯作者：
P. Ungar
加泰罗尼亚语区间和唯一排序的排列
DOI：
--
发表时间：
2019
期刊：
Journal of Combinatorial Theory
影响因子：
--
作者：
Colin Defant
通讯作者：
Colin Defant
使用模式避免机对凯莱排列进行排序
DOI：
--
发表时间：
2020
期刊：
影响因子：
--
作者：
Giulio Cerbai
通讯作者：
Giulio Cerbai