On six expressions of the Tutte polynomial of a graph (on a linearly ordered set of edges)
Abstract
I will present six interrelated general expressions of the Tutte polynomial of a graph, that are available as soon as the set of edges is linearly ordered, and that witness combinatorial properties of such a graph:
- the classical enumeration of spanning tree activities;
- its refinement into a four variable expression in terms of subset activities (that corresponds to the classical partition of the set of edge subsets into boolean intervals);
- the enumeration of orientation-activities for directed graphs;
- its refinement into a four variable expression in terms of subset orientation-activities (that corresponds to the partition of the set of orientations into active partition reversal classes);
- the convolution formula for the Tutte polynomial (that does not need the graph to be ordered);
- and an expression of the Tutte polynomial using only beta invariants of minors (that refines the above expressions).
I will mention that these expressions are all interrelated by the canonical active bijection between spanning trees and orientations, subject of a long-term joint work with Michel Las Vergnas.