Enumerating colorings, tensions and flows in cell complexes
Enumerating colorings, tensions and flows in cell complexes
复制标题
DOI：
10.1016/j.jcta.2013.10.002
复制
发表时间：
2012-12
期刊：
影响因子：
--
通讯作者：
M. Beck;Felix Breuer;Logan Godkin;Jeremy L. Martin
中科院分区：
文献类型：
--
作者：
M. Beck;Felix Breuer;Logan Godkin;Jeremy L. Martin
我们研究了在任意CW-复形X中计数真染色、非零张力和非零流的拟多项式，推广了图的色、张力和流多项式。我们的颜色、张力和流量可以是模数(值以Z/k表示)或整型(值以{−k+1，…，k−1})。在一定的单模条件下，我们得到了色拟多项式、张力拟多项式和流动拟多项式的删除-收缩递推和闭合公式。我们利用几何方法，特别是Ehrhart理论和自内向外多面体，得到了上述所有拟多项式的互易定理，给出了它们在负整数处取值的组合解释以及X的非循环和全循环方向的个数公式。
We study quasipolynomials enumerating proper colorings, nowhere-zero tensions, and nowhere-zero flows in an arbitrary CW-complex X, generalizing the chromatic, tension and flow polynomials of a graph. Our colorings, tensions and flows may be either modular (with values in Z/k Z for some k) or integral (with values in {− k+ 1,…, k− 1}). We obtain deletion–contraction recurrences and closed formulas for the chromatic, tension and flow quasipolynomials, assuming certain unimodularity conditions. We use geometric methods, specifically Ehrhart theory and inside-out polytopes, to obtain reciprocity theorems for all of the aforementioned quasipolynomials, giving combinatorial interpretations of their values at negative integers as well as formulas for the numbers of acyclic and totally cyclic orientations of X.