Parallelogram polyominoes, the sandpile model on a complete bipartite graph, and a q, t-Narayana polynomial
Parallelogram polyominoes, the sandpile model on a complete bipartite graph, and a q, t-Narayana polynomial
复制标题
平行四边形多联骨牌、完全二部图上的沙堆模型以及 q、t-Narayana 多项式
DOI：
10.1016/j.jcta.2013.01.004
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Y. L. Borgne
中科院分区：
文献类型：
--
作者：
M. Dukes;Y. L. Borgne
我们对完整二部图 Km,nin 上的沙堆模型的循环配置进行分类，其中一个指定顶点是汇。我们提出了从这些循环配置到装饰平行四边形多联骨牌的双射，其边界框是 m×n 矩形。通过这种双射检查了几种特殊类型的循环配置及其属性。例如，高度总和最小的循环配置被证明对应于最小面积的多骨牌。另外两类循环配置被证明与双组合矩阵、集合划分的矩阵类似物和 (2+2)-自由偏序集合有关。循环配置的规范倾倒过程会在相关平行四边形多骨牌中产生一条路径。这条路径从多骨骨牌的外部边缘反弹，让人想起哈格伦德著名的戴克路径反弹统计。我们定义了一个多项式集合，称为 q,t-Narayana 多项式，定义为平行四边形多项式集合上的双统计 (area,parabounce) 的生成函数，类似于 Haglund (2003) 中 Dyck 路径上定义的 (area,hagbounce) 双统计。在此过程中，我们扩展了 Egge 等人的双统计。 (2003) 平行四边形多骨牌集合。这是他们关于扩展其他组合对象的问题的一个答案。我们猜想 q,t-Narayana 多项式是对称的，并在许多特殊情况下证明了这个猜想。我们还展示了戴克路径上的哈格伦德（面积，hagbounce）统计量与生活在 (n+1)×n 矩形中的平行四边形多骨牌子集的双统计量（面积，parabounce）之间的关系。
We classify recurrent configurations of the sandpile model on the complete bipartite graph Km,nin which one designated vertex is a sink. We present a bijection from these recurrent configurations to decorated parallelogram polyominoes whose bounding box is an m×n rectangle. Several special types of recurrent configurations and their properties via this bijection are examined. For example, recurrent configurations whose sum of heights is minimal are shown to correspond to polyominoes of least area. Two other classes of recurrent configurations are shown to be related to bicomposition matrices, a matrix analogue of set partitions, and (2+2)-free partially ordered sets. A canonical toppling process for recurrent configurations gives rise to a path within the associated parallelogram polyominoes. This path bounces off the external edges of the polyomino, and is reminiscent of Haglundʼs well-known bounce statistic for Dyck paths. We define a collection of polynomials that we call q,t-Narayana polynomials, defined to be the generating function of the bistatistic (area,parabounce) on the set of parallelogram polyominoes, akin to the (area,hagbounce) bistatistic defined on Dyck paths in Haglund (2003). In doing so, we have extended a bistatistic of Egge et al. (2003) to the set of parallelogram polyominoes. This is one answer to their question concerning extensions to other combinatorial objects. We conjecture the q,t-Narayana polynomials to be symmetric and prove this conjecture for numerous special cases. We also show a relationship between Haglundʼs (area,hagbounce) statistic on Dyck paths, and our bistatistic (area,parabounce) on a sub-collection of those parallelogram polyominoes living in a (n+1)×n rectangle.