On six expressions of the Tutte polynomial of a graph (on a linearly ordered set of edges) - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2016

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

Emeric Gioan

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.
No file

Dates and versions

lirmm-01370263 , version 1 (22-09-2016)

Identifiers

  • HAL Id : lirmm-01370263 , version 1

Cite

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⟩
128 View
0 Download

Share

Gmail Facebook X LinkedIn More