Fourientation activities and the Tutte polynomial

Sam Hopkins (MIT)

Abstract :

This talk is based on joint work with Spencer Backman and Lorenzo Traldi. The Tutte polynomial, a kind of two-variable generalization of the chromatic polynomial, is one of the most important polynomials associated to a graph. One straightforward definition, the corank-nullity expansion, expresses the Tutte polynomial as a sum over all (spanning) subgraphs. Tutte's original definition, however, was as a sum over spanning trees weighted by internal and external activity. In 1990 Gordon and Traldi found a "generalized activities" expansion of the Tutte polynomial that recovers both of these definitions. Meanwhile, it has been known that the Tutte polynomial is intimately related to graph orientations since at least the seminal work of Stanley expressing the number of acyclic orientations as a Tutte polynomial evaluation. Las Vergnas generalized Stanley's result by expressing the Tutte polynomial as a sum over all orientations weighted by "orientation activities." We provide a common generalization of the Gordon-Traldi and Las Vergnas formulas by expressing the Tutte polynomial as a sum over fourientations weighted by their activities. A fourientation is a hybrid between a subgraph and a orientation: it is a choice for each edge whether to orient that edge in either direction, leave it unoriented, or biorient it. Via this fourientation activities formula we recapture early work with Spencer Backman which says that various "min edge" classes of fourientations are enumerated by the Tutte polynomial. These min edge classes arise in connection with many geometric and algebraic objects associated to a graph including bigraphical hyperplane arrangements, cycle-cocycle reversal systems, graphic Lawrence ideals and zonotopal algebras. Time permitting, I will discuss some of these connections.