On six expressions of the Tutte polynomial of a graph (on a linearly ordered set of edges)

Emeric Gioan 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01370263
Contributor : Emeric Gioan <>
Submitted on : Thursday, September 22, 2016 - 11:56:56 AM
Last modification on : Thursday, May 24, 2018 - 3:59:22 PM

Identifiers

  • HAL Id : lirmm-01370263, version 1

Collections

Citation

Emeric Gioan. On six expressions of the Tutte polynomial of a graph (on a linearly ordered set of edges). Graph Polynomials: Towards a Comparative Theory, Jun 2016, Dagstuhl seminar, Germany. ⟨lirmm-01370263⟩

Share

Metrics

Record views

111