论文标题
关于Posets的促销和准划界标签
On Promotion and Quasi-tangled Labelings of Posets
论文作者
论文摘要
2022年，防御者和克拉维兹（Kravitz）引入了扩展促销活动（表示为$ \ partial $），该地图作用于Poset的一组标签。扩展促销是对Schützenberger的促销操作员的概括，这是一张经过良好研究的地图，它列入了Poset的线性扩展集。众所周知，如果$ l $是$ n $ element poset $ p $的标签，则$ \ partial^{n-1}（l）$是线性扩展。这使我们可以将$ \ partial $视为$ p $所有标签集的分类运算符，我们认为$ p $的线性扩展名为已分类的标签。需要分类的$ \ partial $的$ n-1 $应用的标签称为Tangled；需要$ N-2 $应用程序的标签称为准缠结。除了计算植根树poset的促进纤维的尺寸外，我们还计算了一个相对较大的Poset的准标记，称为膨胀的有叶的叶子，带有放气叶子。给定一个$ n $ element Poset具有独特的最小元素，其属性最小元素具有一个父母，因此，从上述枚举中，该Poset的$ 2（n-1）！ - （n-2）！$ quasi tangnangled标签。使用类似的方法，我们概述了一种算法方法来列举要求为任何固定的$ k \ in \ {1，\ ldots，n-2 \} $进行排序的标签。我们还取得了部分进步，以证明猜想的猜想和克拉维兹（Kravitz），以$ n $ element Poset的最大纠结标签数量。
In 2022, Defant and Kravitz introduced extended promotion (denoted $\partial$), a map that acts on the set of labelings of a poset. Extended promotion is a generalization of Schützenberger's promotion operator, a well-studied map that permutes the set of linear extensions of a poset. It is known that if $L$ is a labeling of an $n$-element poset $P$, then $\partial^{n-1}(L)$ is a linear extension. This allows us to regard $\partial$ as a sorting operator on the set of all labelings of $P$, where we think of the linear extensions of $P$ as the labelings which have been sorted. The labelings requiring $n-1$ applications of $\partial$ to be sorted are called tangled; the labelings requiring $n-2$ applications are called quasi-tangled. In addition to computing the sizes of the fibers of promotion for rooted tree posets, we count the quasi-tangled labelings of a relatively large class of posets called inflated rooted trees with deflated leaves. Given an $n$-element poset with a unique minimal element with the property that the minimal element has exactly one parent, it follows from the aforementioned enumeration that this poset has $2(n-1)!-(n-2)!$ quasi-tangled labelings. Using similar methods, we outline an algorithmic approach to enumerating the labelings requiring $n-k-1$ applications to be sorted for any fixed $k\in\{1,\ldots,n-2\}$. We also make partial progress towards proving a conjecture of Defant and Kravitz on the maximum possible number of tangled labelings of an $n$-element poset.
