A Characterization of the Tutte Polynomial via Combinatorial Embeddings

By Olivier Bernardi. 2006

54 citations recorded by the source corpus.

Abstract.We give a new characterization of the Tutte polynomial of graphs. Our characterization is formally close (but inequivalent) to the original definition given by Tutte as the generating function of spanning trees counted according to activities. Tutte’s notion of activity requires a choice of a linear order on the edge set (though the generating function of the activities is, in fact, independent of this order). We define a new notion of activity, the embedding-activity, which requires a choice of a combinatorial embedding of the graph, that is, a cyclic order of the edges around each vertex. We prove that the Tutte polynomial equals the generating function of spanning trees counted according to embedding-activities. This generating function is, in fact, independent of the embedding.

Subfields: Computational Theory and Mathematics, Condensed Matter Physics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/cdba1c2072b3876a415770d8e677ba7a3af8282f