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.
Metrics
2 Record Views
Details
Title
Generalized Whitney formulas for broken circuits in ambigraphs and matroids
Creators
Darij Grinberg
Publication Details
arXiv.org
Resource Type
Preprint
Language
English
Academic Unit
Mathematics
Other Identifier
991021862368704721
Research Home Page
Browse by research and academic units
Learn about the ETD submission process at Drexel
Learn about the Libraries’ research data management services