Combinatorial reciprocity for the chromatic polynomial and the chromatic symmetric function
Combinatorial reciprocity for the chromatic polynomial and the chromatic symmetric function
复制标题
DOI：
10.1016/j.disc.2020.111989
复制
发表时间：
2019-04
期刊：
影响因子：
--
通讯作者：
O. Bernardi;Philippe Nadeau
中科院分区：
文献类型：
--
作者：
O. Bernardi;Philippe Nadeau
设G是一个图，χG是它的色多项式。对于任意非负整数i，j，我们用非循环方向给出了赋值χG(I)(−j)的一个解释。这恢复了斯坦利以及格林和扎斯拉夫斯基分别在i=0和j=0的情况下的经典解释。我们还给出了我们的解释的对称函数求精，以及一些推广。这些证明遵循了1999年Gessel的一篇论文的精神，使用了堆理论。
Let G be a graph, and let χ G be its chromatic polynomial. For any non-negative integers i, j, we give an interpretation for the evaluation χ G (i)(− j) in terms of acyclic orientations. This recovers the classical interpretations due to Stanley and to Greene and Zaslavsky respectively in the cases i= 0 and j= 0. We also give symmetric function refinements of our interpretations, and some extensions. The proofs use heap theory in the spirit of a 1999 paper of Gessel.