Files and links (1)
Preprint (Author's original)arXiv.org - Non-exclusive license to distribute, Open
Preprint
Generalized Whitney formulas for broken circuits in ambigraphs and matroids
arXiv.org
11 Apr 2016
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.
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