Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-26T17:04:35.840Z Has data issue: false hasContentIssue false
  • English
  • Français

A Tutte Polynomial for Maps

Published online by Cambridge University Press:  12 April 2018

ANDREW GOODALL ,
THOMAS KRAJEWSKI ,
GUUS REGTS  and
LLUÍS VENA
ANDREW GOODALL
Affiliation:
Computer Science Institute, Charles University, Prague, Czech Republic (e-mail: [email protected])
THOMAS KRAJEWSKI
Affiliation:
Aix-Marseille Université, Université de Toulon, CNRS, CPT, Marseille, France (e-mail: [email protected])
GUUS REGTS
Affiliation:
Department of Mathematics, University of Amsterdam, Amsterdam, Netherlands (e-mail: [email protected])
LLUÍS VENA
Affiliation:
Computer Science Institute, Charles University, Prague, Czech Republic (e-mail: [email protected]) Faculty of Science, University of Amsterdam, Amsterdam, Netherlands (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

We follow the example of Tutte in his construction of the dichromate of a graph (i.e. the Tutte polynomial) as a unification of the chromatic polynomial and the flow polynomial in order to construct a new polynomial invariant of maps (graphs embedded in orientable surfaces). We call this the surface Tutte polynomial. The surface Tutte polynomial of a map contains the Las Vergnas polynomial, the Bollobás–Riordan polynomial and the Krushkal polynomial as specializations. By construction, the surface Tutte polynomial includes among its evaluations the number of local tensions and local flows taking values in any given finite group. Other evaluations include the number of quasi-forests.

Keywords

Primary 05C31Secondary 05C1057M15
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 27 , Issue 6 , November 2018 , pp. 913 - 945
Copyright
Copyright © Cambridge University Press 2018 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

†

Supported by Project ERCCZ LL1201 Cores and the Czech Science Foundation, GA ČR 16-19910S.

‡

Supported by ANR grant ANR JCJC ‘CombPhysMat2Tens’.

§

Supported by the European Research Council under the European Union's Seventh Framework Programme (FP7/2007-2013) / ERC grant agreement 339109, and by an NWO Veni grant.

Supported by the Center of Excellence–Institute for Theoretical Computer Science, Prague, P202/12/G061, and by Project ERCCZ LL1201 Cores.

‖

The research leading to these results received funding from the European Research Council under the European Union's Seventh Framework Programme (FP7/2007-2013) / ERC grant agreement 339109.

References

[1] Askanazi, R., Chmutov, S., Estill, C., Michel, J. and Stollenwerk, P. (2013) Polynomial invariants of graphs on surfaces. Quantum Topol. 4 77–90.Google Scholar
[2] Biggs, N. (1993) Algebraic Graph Theory, second edition, Cambridge Mathematical Library, Cambridge University Press.Google Scholar
[3] Bollobás, B. (1998) Modern Graph Theory, Vol. 184 of Graduate Texts in Mathematics, Springer.Google Scholar
[4] Bollobás, B. and Riordan, O. (2001) A polynomial invariant of graphs on orientable surfaces. Proc. London Math. Soc. (3) 83 513–531.Google Scholar
[5] Bollobás, B. and Riordan, O. (2002) A polynomial of graphs on surfaces. Math. Ann. 323 81–96.Google Scholar
[6] Bouchet, A. (1989) Maps and ▵-matroids. Discrete Math. 78 59–71.Google Scholar
[7] Butler, C. (2018) A quasi-tree expansion of the Krushkal polynomial. Adv. in Appl. Math., 94 3–22.Google Scholar
[8] Champanerkar, A., Kofman, I. and Stoltzfus, N. (2011) Quasi-tree expansion for the Bollobás–Riordan–Tutte polynomial. Bull. Lond. Math. Soc. 43 972–984.Google Scholar
[9] Chun, C., Moffatt, I., Noble, S. and Rueckeriemen, R. (2016) Matroids, delta-matroids and embedded graphs. arXiv:1403.0920Google Scholar
[10] DeVos, M. J. (2000) Flows on graphs. PhD thesis, Princeton University.Google Scholar
[11] Edmonds, J. K. (1960) A Combinatorial Representation for Polyhedral Surfaces, Notices of the American Mathematical Society, AMS.Google Scholar
[12] Ellis-Monaghan, J. A. and Merino, C. (2011) Graph polynomials and their applications I: The Tutte polynomial. In Structural Analysis of Complex Networks, Birkhäuser/Springer, pp. 219–255.Google Scholar
[13] Ellis-Monaghan, J. A. and Moffatt, I. (2013) Graphs on Surfaces, Springer Briefs in Mathematics, Springer.Google Scholar
[14] Ellis-Monaghan, J. A. and Moffatt, I. (2015) The Las Vergnas polynomial for embedded graphs. European J. Combin. 50 97–114.Google Scholar
[15] Frobenius, G. (1896) Über Gruppencharaktere. Sitzber. Königlich Preuss Akad. Wiss. Berlin, pp. 985–1021.Google Scholar
[16] Goodall, A., Litjens, B., Regts, G. and Vena, L. (2017) A Tutte polynomial for non-orientable maps. Electron. Notes Discrete Math. 61 513–519.Google Scholar
[17] Hatcher, A. (2002) Algebraic Topology, Cambridge University Press.Google Scholar
[18] Jones, G. A. (1998) Characters and surfaces: A survey. In The Atlas of Finite Groups: Ten Years On, Vol. 249 of London Mathematical Society Lecture Note Series, Cambridge University Press, pp. 90–118.Google Scholar
[19] Kochol, M. (2002) Polynomials associated with nowhere-zero flows. J. Combin. Theory Ser. B 84 260–269.Google Scholar
[20] Krushkal, V. (2011) Graphs, links, and duality on surfaces. Combin. Probab. Comput. 20 267–287.Google Scholar
[21] Lando, S. K. and Zvonkin, A. K. (2004) Graphs on Surfaces and their Applications, Vol. 141 of Encyclopaedia of Mathematical Sciences, Springer.Google Scholar
[22] Las Vergnas, M. (1978) Sur les activités des orientations d'une géométrie combinatoire. Cahiers Centre Études Rech. Opér. 20 293–300.Google Scholar
[23] Las Vergnas, M. (1980) On the Tutte polynomial of a morphism of matroids, Ann. Discrete Math. 8 7–20.Google Scholar
[24] Litjens, B. (2017) On dihedral flows in embedded graphs. arXiv:1709.06469Google Scholar
[25] Litjens, B. and Sevenster, B. Partition functions and a generalized coloring-flow duality for embedded graphs. J. Graph Theory. http://doi.org/10.1002/jgt.22210Google Scholar
[26] Mednyh, A. D. (1978) Determination of the number of nonequivalent coverings over a compact Riemann surface. Dokl. Akad. Nauk SSSR 239 269–271.Google Scholar
[27] Mulase, M. and Yu, J. T. (2005) Non-commutative matrix integrals and representation varieties of surface groups in a finite group. Ann. Inst. Fourier (Grenoble) 55 2161–2196.Google Scholar
[28] Noble, S. D. and Welsh, D. J. A. (1999) A weighted graph polynomial from chromatic invariants of knots. Ann. Inst. Fourier (Grenoble) 49 1057–1087.Google Scholar
[29] Oxley, J. G. and Welsh, D. J. A. (1979) The Tutte polynomial and percolation. In Graph Theory and Related Topics (Bondy, J. A. et al., eds), Academic Press, pp. 329–339.Google Scholar
[30] Serre, J.-P. (2012) Linear Representations of Finite Groups, Vol. 42 of Graduate Texts in Mathematics, Springer.Google Scholar
[31] Tutte, W. T. (1947) A ring in graph theory. Proc. Cambridge Philos. Soc. 43 26–40.Google Scholar
[32] Tutte, W. T. (1949) On the imbedding of linear graphs in surfaces. Proc. London Math. Soc. (2) 51 474–483.Google Scholar
[33] Tutte, W. T. (1954) A contribution to the theory of chromatic polynomials. Canad. J. Math. 6 80–91.Google Scholar
[34] Tutte, W. T. (2001) Graph Theory, Vol. 21 of Encyclopedia of Mathematics and its Applications, Cambridge University Press.Google Scholar
[35] Tutte, W. T. (2004) Graph-polynomials. Adv. Appl. Math. 32 5–9.Google Scholar
[36] Watanabe, Y. and Fukumizu, K. (2011) New graph polynomials from the Bethe approximation of the Ising partition function. Combin. Probab. Comput. 20 299–320.Google Scholar
[37] Welsh, D. J. A. (1993) Complexity: Knots, Colourings and Counting, Vol. 186 of London Mathematical Society Lecture Note Series, Cambridge University Press.Google Scholar
[38] Welsh, D. J. A. (1999) The Tutte polynomial. Random Struct. Alg. 15 210–228.Google Scholar
[39] Whitney, H. (1932) Non-separable and planar graphs. Trans. Amer. Math. Soc. 34 339–362.Google Scholar