Mathematics > Combinatorics
arXiv:1604.03063 (math)
[Submitted on 11 Apr 2016 (v1), last revised 16 Jun 2026 (this version, v3)]
Abstract:We explore several generalizations of Whitney's theorem -- a classical formula for the chromatic polynomial of a graph. Following Stanley, we replace the chromatic polynomial by the chromatic symmetric function. Following Dohmen and Trinks, we exclude not all but only an (arbitrarily selected) set of broken circuits, or even weigh these broken circuits with weight monomials instead of excluding them. Following Crew and Spirkl, we put weights on the vertices of the graph. Following Gebhard and Sagan, we lift the chromatic symmetric function to noncommuting variables. In addition, we replace the graph by an "ambigraph", an apparently new concept that includes both hypergraphs and multigraphs as particular cases.
We show that Whitney's formula endures all these generalizations, and a fairly simple sign-reversing involution can be used to prove it in each setting. Furthermore, if we restrict ourselves to the chromatic polynomial, then the graph can be replaced by a matroid.
We discuss an application to transitive digraphs (i.e., posets), and reprove an alternating-sum identity by Dahlberg and van Willigenburg.
| Comments: | 99 pages, self-contained, with lots of space taken up by defining several parallel settings. The definitions of an ambigraph and its characteristic polynomial (Section 5.1) is likely of independent interest. v3 corrects typos found by GPT-5.5 |
| Subjects: | Combinatorics (math.CO) |
| MSC classes: | 05E05, 05B35, 05C15 |
| Cite as: | arXiv:1604.03063 [math.CO] |
| (or arXiv:1604.03063v3 [math.CO] for this version) | |
| https://doi.org/10.48550/arXiv.1604.03063 arXiv-issued DOI via DataCite |
Submission history
From: Darij Grinberg [view email]
[v1]
Mon, 11 Apr 2016 18:45:05 UTC (69 KB)
[v2]
Fri, 5 May 2023 01:19:44 UTC (1,064 KB)
[v3]
Tue, 16 Jun 2026 06:08:14 UTC (1,068 KB)
Current browse context:
math.CO
Bookmark
Bibliographic Tools
Bibliographic and Citation Tools
Bibliographic Explorer Toggle
Code, Data, Media
Code, Data and Media Associated with this Article
Demos
Demos
Related Papers
Recommenders and Search Tools
About arXivLabs
arXivLabs: experimental projects with community collaborators
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.