Enumerating Colorings, Tensions and Flows in Cell Complexes
Issue Date
2014-02Author
Beck, Matthias
Breuer, Felix
Godkin, Logan
Martin, Jeremy L.
Publisher
Elsevier
Type
Article
Article Version
Scholarly/refereed, author accepted manuscript
Metadata
Show full item recordAbstract
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/kZZ/kZ for some k) or integral (with values in {−k+1,…,k−1}{−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.
Description
this is the author's final draft. Copyright 2014 Elsevier.
Collections
Citation
Beck, Matthias, Felix Breuer, Logan Godkin, and Jeremy L. Martin. "Enumerating Colorings, Tensions and Flows in Cell Complexes." Journal of Combinatorial Theory, Series A 122 (2014): 82-106. doi:10.1016/j.jcta.2013.10.002.
Items in KU ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.
We want to hear from you! Please share your stories about how Open Access to this item benefits YOU.