偏序集关联多面体与栈排序

《Discrete Mathematics》：Poset associahedra and stack-sorting

　　摘要
对于任何有限的连通偏序集P，Galashin引入了一个简单的凸多面体A(P)，其维度为(|P|?2)，称为偏序集关联多面体。对于某些偏序集家族，它们的偏序集关联多面体介于经典的排列多面体和关联多面体之间，我们给出了h-向量的一个简单的组合解释。我们的解释与排列的堆叠排序理论有关，同时也允许我们证明它们的一些h-多项式的实根性。

引言
对于任何有限的连通偏序集P，Galashin引入了偏序集关联多面体A(P)（参见[4]）。A(P)的面对应于P的管状结构，而A(P)的顶点对应于P的最大管状结构；具体定义见第2.2节。A(P)也可以被描述为保持顺序的映射P→R的配置空间的紧化。许多多面体可以被描述为偏序集关联多面体，包括排列多面体和关联多面体。特别是当P是爪形偏序集时，即P由一个唯一的最小元素0和n个两两不相等的元素组成，那么A(P)就是n-排列多面体。另一方面，当P是一个包含n+1个元素的链时，即P=Cn+1，那么A(P)就是关联多面体Kn+1。在众多的h-向量（h0,h1,…,hn?1）的组合解释中，我们想要回顾以下解释：hi计算了具有恰好i个下降的2^31-避免排列的数量。

堆叠排序是一个函数s:Sn→Sn，它试图在线性时间内对Sn中的排列w进行排序，但不总是完全排序（具体定义见第2.4节）。如果s(w)=1^2…n，则排列w是可堆叠排序的。众所周知，可堆叠排序的排列正是2^31-避免排列。因此，我们对A(Cn+1)的h-向量有另一种解释：hi计算了在s^(-1)(1^2…n)中具有恰好i个下降的排列的数量。

本文的重点是偏序集An,k=Cn+1⊕Ak，其中Ak是包含k个元素的反链。特别是，A0,k是一个爪形偏序集，而An,0是一个链Cn+1。令人惊讶的是，A(An,k)的h-向量也可以通过堆叠排序原像的下降次数来计数。设Sn,k={w|w∈Sn+k, wi=ifor all i>k}，我们证明了上述经典结果的以下推广。

定理4.8
设h=(h0,h1,…,hn+k?1)是A(An,k)的h-向量。那么hi计算了在s^(-1)(Sn,k)中具有恰好i个下降的排列的数量。

备注1.1
我们感谢一位匿名审稿人指出现Sn,k可以被视为An,k的哈塞图边的线性扩展集合L(An,k)。虽然一般来说A(P)的h-向量并不总是计算s^(-1)(L(P))中的下降次数（参见[6]中的命题5.9作为反例），但进一步研究这一现象是很有趣的。

定理4.8的一个直接推论是A(An,k)的γ-非负性。特别是，我们有以下由Br?ndén得出的结果：
定理4.9 [3]
对于A?Sn，我们有∑σ∈s^(-1)(A)xdes(σ)=∑m=0?n?1/2?{|σ∈s^(-1)(A):peak(σ)=m}|^(2n?1?2m)，其中peak(σ)是指满足σi?1<σi>σi+1的索引i的数量。因此，我们有了以下推论的另一种证明。我们注意到这个推论也可以从[7]中的定理11.6得出（见备注4.11）。

推论4.10
A(An,k)的γ-向量是非负的。

此外，在证明定理4.8的过程中，我们找到了s^(-1)(Sn,k)的大小与k!和Catalan卷积Cn(k)之间的关系，Cn(k)将在第2.5节中介绍。

推论3.3
对于所有n,k≥0，我们有|s^(-1)(Sn,k)|=k!?Cn(k)。注意Cn(0)是经典的Catalan数Cn。因此，将k=0代入推论3.3中，我们得到了经典结果s^(-1)(1^2…n)=Cn。最后，在第5节中，我们将利用堆叠排序中的一个“巧合”来证明A(An,2)的h-多项式的实根性。

定理5.4
设Hn(x)是A(An,2)的h-多项式。那么，Hn(x)是实根的。

多面体和面数
凸多面体P是Rn中有限点集的凸包。多面体的维度是其仿射张成的维度。凸多面体P的面F是P中某个线性函数取得最大值的点集。由单个点组成的面称为顶点，一维面称为边。如果P的任何顶点恰好与d条边相邻，则称d维多面体P为简单多面体。

对于d维多面体P，面数fi指的是...

堆叠排序
回想一下，我们定义了Sn,k={w|w∈Sn+k, wi=ifor all i>k}。在本节中，我们将构建一个从s^(-1)(Sn,k)到Pn,k的双射，该双射保持下降次数不变。

对于w∈s^(-1)(Sn,k)，设T=I^(-1)(w)是对应于w的递减二叉树。定义T的核心树为由节点k+1,…,n+k诱导的子树。注意T的核心树是连通的，并且节点必须按后序从k+1标到n+k。如果核心树中的节点包含节点k+1，则该节点被标记为...

现在我们转向偏序集关联多面体的面数。回想一下，两个偏序集(P,< />< />s对于所有s∈S，要么•p
当自主子集是一个链或反链时，有以下有趣的恒等式：

定理6.1 [6, 定理3.1]
设p是一个具有大小为n的自主子集s的偏序集，即s=cak。

致谢
作者感谢vic reiner和pavel galashin的指导。我们还要感谢colin defant在堆叠排序方面的有益讨论。

son nguyen | andrew sack 当自主子集是一个链或反链时，有以下有趣的恒等式： 定理6.1 [6, 定理3.1] 设p是一个具有大小为n的自主子集s的偏序集，即s=CAk。 致谢 作者感谢vic reiner和pavel galashin的指导。我们还要感谢colin defant在堆叠排序方面的有益讨论。 son nguyen | andrew>
当自主子集是一个链或反链时，有以下有趣的恒等式：

定理6.1 [6, 定理3.1]
设p是一个具有大小为n的自主子集s的偏序集，即s=cak。

致谢
作者感谢vic reiner和pavel galashin的指导。我们还要感谢colin defant在堆叠排序方面的有益讨论。

son nguyen | andrew sack>