<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 12 Issue 1" %>
A Characterization of the Tutte Polynomial via Combinatorial Embeddings
Olivier Bernardi
LaBRI, Universit\'{e} Bordeaux 1, 351 cours de la Lib\'{e} ration, 33405 Talence cedex, France
Annals of Combinatorics 12 (2) p.133-147 March, 2008
AMS Subject Classification: 05C99
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.
Keywords: Tutte polynomial, spanning trees, activities, embedded graphs


1. R.J. Baxter, Exactly Solved Model in Statistical Mechanics, Academic Press, London, 1982.

2. R.J. Baxter, Dichromatic polynomials and Potts models summed over rooted maps, Ann. Combin. 5 (1) (2001) 17--–36.

3. O. Bernardi, Tutte polynomial, subgraphs, orientations and sandpile model: new connections via embeddings, arXiv: math.CO/0612003.

4. O. Bernardi, Bijective counting of tree-rooted maps and shufes of parenthesis systems, Electron. J. Combin. 14 (1) (2007) #R9.

5. B. Bollob´as, Modern Graph Theory, In: Graduate Texts in Mathematics, Vol. 184, Springer- Verlag, New York, 1998.

6. B. Bollob´as and O. Riordan, A polynomial invariant of graphs on orientable surfaces, Proc. London Math. Soc. (3) 83 (3) (2001) 513--–531.

7. G. Bonnet and B. Eynard, The Potts-q random matrix model: loop equations, critical exponents, and rational case, Phys. Lett. B 463 (2-4) (1999) 273--–279.

8. T. Brylawski and J.G. Oxley, The Tutte polynomial and its applications, In: Matroid Applications, N. White, Ed., Cambridge Univ. Press, London, 1992.

9. R. Cori and A. Machì, Maps, hypermaps and their automorphisms: a survey. I, II, III, Exposition. Math. 10 (5) (1992) 403–427, 429–447, 449--–467.

10. J.M. Daul, Q-states Potts model on a random planar lattice, arXiv: hep-th/9502014.

11. C.M. Fortuin and P.W. Kasteleyn, On the random cluster model. I. Introduction and relation to other models, Physica, 57 (1972) 536--–564.

12. I.M. Gessel, Enumerative applications of a decomposition for graphs and digraphs, Discrete Math. 139 (1-3) (1995) 257--–271.

13. I.M. Gessel and B.E. Sagan, The Tutte polynomial of a graph, depth-first search, and simplicial complex partitions, Electron. J. Combin. 3 (2) (1996) #R9.

14. I.M. Gessel and D.L. Wang, Depth-first search as a combinatorial correspondence, J. Combin. Theory Ser. A 26 (3) (1979) 308–--313.

15. E. Gioan and M. Las Vergnas, Activity preserving bijections between spanning trees and orientations in graphs, Discrete Math. 298 (1-3) (2005) 169--–188.

16. D. Kostic and C.H. Yan, Multiparking functions, graph searching and the tutte polynomial, Adv. Appl. Math. 40 (1) (2008) 73--–97.

17. M. Las Vergnas, A correspondence between spanning trees and orientations in graphs, In: Graph Theory and Combinatorics, Academic Press, London, (1984) pp. 233–--238.

18. M. Las Vergnas, The Tutte polynomial of a morphism of matroids II. Activities of orientations, In: Progress in Graph Theory, J.A. Bondy and U.S.R. Murty Eds., Academic Press, Toronto, (1984) pp. 367--380.

19. A.B. Lehman and T.R.S. Walsh, Counting rooted maps by genus II, J. Combin. Theory Ser. B 13 (1972) 122--–141.

20. B. Mohar and C. Thomassen, Graphs on Surfaces, J. Hopkins Univ. Press, Baltimore, 2001.

21. R.C. Mullin, On the enumeration of tree-rooted maps, Canad. J. Math. 19 (1967) 174–--183.

22. A.D. Sokal, The multivariate Tutte polynomial (alias Potts model) for graphs and matroids, In: Surveys in Combinatorics, Bridget S.Webb Ed., Cambridge Univ. Press, London, (2005) pp. 173--–226.

23. W.T. Tutte, A ring in graph theory, Proc. Cambridge Philos. Soc. 43 (1947) 26--–40.

24. W.T. Tutte, A contribution to the theory of chromatic polynomials, Canad. J. Math. 6 (1954) 80--–91.

25. W.T. Tutte, Graph-polynomials, Adv. Appl. Math. 32 (2004) 5--–9.