论文标题
促销排序
Promotion Sorting
论文作者
论文摘要
Schützenberger的促销操作员是一个广泛研究的两者，可置入有限孔的线性扩展。我们引入了该操作员的天然扩展名$ \ partial $，该$ $ \ topial $均在poset的所有标签上。我们证明了$ \ partial $的几个属性；特别是，我们表明，对于$ n $ element poset $ p $的每个标签$ l $，标签$ \ partial^{n-1}（l）$是$ p $的线性扩展。因此，我们可以将由$ \ partial $定义的动态系统视为将标记为线性扩展的排序过程。对于所有$ 0 \ leq k \ leq n-1 $，我们表征了$ n $ element posets $ p $，这些标签允许至少需要$ n-k-1 $ tererations $ \ partial $迭代，以便成为线性扩展。 $ k = 0 $涉及需要最大可能迭代数量才能排序的标签；我们称这些标签纠结。我们明确列举了一大批我们称为膨胀的森林posets的纠结标签。对于任意有限的POSET，我们展示了如何枚举可排序标签，这是标签$ l $，以使$ \ partial（l）$是线性扩展。
Schützenberger's promotion operator is an extensively-studied bijection that permutes the linear extensions of a finite poset. We introduce a natural extension $\partial$ of this operator that acts on all labelings of a poset. We prove several properties of $\partial$; in particular, we show that for every labeling $L$ of an $n$-element poset $P$, the labeling $\partial^{n-1}(L)$ is a linear extension of $P$. Thus, we can view the dynamical system defined by $\partial$ as a sorting procedure that sorts labelings into linear extensions. For all $0\leq k\leq n-1$, we characterize the $n$-element posets $P$ that admit labelings that require at least $n-k-1$ iterations of $\partial$ in order to become linear extensions. The case in which $k=0$ concerns labelings that require the maximum possible number of iterations in order to be sorted; we call these labelings tangled. We explicitly enumerate tangled labelings for a large class of posets that we call inflated rooted forest posets. For an arbitrary finite poset, we show how to enumerate the sortable labelings, which are the labelings $L$ such that $\partial(L)$ is a linear extension.
