Hostname: page-component-586b7cd67f-gb8f7 Total loading time: 0 Render date: 2024-11-24T18:58:51.044Z Has data issue: false hasContentIssue false
  • English
  • Français

Evaluations of Topological Tutte Polynomials

Published online by Cambridge University Press:  10 October 2014

J. ELLIS-MONAGHAN  and
I. MOFFATT
J. ELLIS-MONAGHAN
Affiliation:
Department of Mathematics, Saint Michael's College, 1 Winooski Park, Colchester, VT 05439, USA (e-mail: [email protected])
I. MOFFATT
Affiliation:
Department of Mathematics, Royal Holloway, University of London, Egham, Surrey, TW20 0EX, UK (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

We find new properties of the topological transition polynomial of embedded graphs, Q(G). We use these properties to explain the striking similarities between certain evaluations of Bollobás and Riordan's ribbon graph polynomial, R(G), and the topological Penrose polynomial, P(G). The general framework provided by Q(G) also leads to several other combinatorial interpretations these polynomials. In particular, we express P(G), R(G), and the Tutte polynomial, T(G), as sums of chromatic polynomials of graphs derived from G, show that these polynomials count k-valuations of medial graphs, show that R(G) counts edge 3-colourings, and reformulate the Four Colour Theorem in terms of R(G). We conclude with a reduction formula for the transition polynomial of the tensor product of two embedded graphs, showing that it leads to additional relations among these polynomials and to further combinatorial interpretations of P(G) and R(G).

Keywords

Primary 05C31Secondary 05C10
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 24 , Issue 3 , May 2015 , pp. 556 - 583
Copyright
Copyright © Cambridge University Press 2014 

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.)

References

[1]Aigner, M. (1997) The Penrose polynomial of a plane graph. Math. Ann. 307 173–189.CrossRefGoogle Scholar
[2]Aigner, M. (2000) Die Ideen von Penrose zum 4-Farbenproblem. Jahresber. Deutsch. Math.-Verein. 102 43–68.Google Scholar
[3]Bollobás, B. and Riordan, O. (2001) A polynomial invariant of graphs on orientable surfaces. Proc. London Math. Soc. 83 513–531.Google Scholar
[4]Bollobás, B. and Riordan, O. (2002) A polynomial of graphs on surfaces. Math. Ann. 323 81–96.CrossRefGoogle Scholar
[5]Brylawski, T. (1982) The Tutte polynomial I: General theory. In Matroid Theory and its Applications, Liguori, Naples, pp. 125–275.Google Scholar
[6]Chmutov, S. (2009) Generalized duality for graphs on surfaces and the signed Bollobás–Riordan poly-nomial. J. Combin. Theory Ser. B 99 617–638.Google Scholar
[7]Chmutov, S. and Pak, I. (2007) The Kauffman bracket of virtual links and the Bollobás–Riordan poly-nomial. Mosc. Math. J. 7 409–418.Google Scholar
[8]Dasbach, O. T., Futer, D., Kalfagianni, E., Lin, X.-S. and Stoltzfus, N. W. (2008) The Jones polynomial and graphs on surfaces. J. Combin. Theory Ser. B 98 384–399.Google Scholar
[9]Ellis-Monaghan, J. A. (1998) New results for the Martin polynomial. J. Combin. Theory Ser. B 74 326–352.CrossRefGoogle Scholar
[10]Ellis-Monaghan, J. A. and Moffatt, I. (2012) Twisted duality for embedded graphs. Trans. Amer. Math. Soc. 364 1529–1569.CrossRefGoogle Scholar
[11]Ellis-Monaghan, J. A. and Moffatt, I. (2013) A Penrose polynomial for embedded graphs. European J. Combin. 34 424–445.CrossRefGoogle Scholar
[12]Ellis-Monaghan, J. A. and Sarmiento, I. (2002) Generalized transition polynomials. Congr. Numer. 155 57–69.Google Scholar
[13]Ellis-Monaghan, J. A. and Sarmiento, I. (2011) A recipe theorem for the topological Tutte polynomial of Bollobás and Riordan. European J. Combin. 32 782–794.Google Scholar
[14]Huggett, S. and Moffatt, I. (2011) Expansions for the Bollobás–Riordan and Tutte polynomials of separable ribbon graphs. Ann. Comb. 15 675–706.Google Scholar
[15]Jaeger, F. (1988) On Tutte polynomials and cycles of plane graphs. J. Combin. Theory Ser. B 44 127–146.Google Scholar
[16]Jaeger, F. (1990) On transition polynomials of 4-regular graphs. In Cycles and Rays, Vol. 301 of NATO Adv. Sci. Inst. Ser. C, Math. Phys. Sci, Kluwer Academic, pp. 123–150.CrossRefGoogle Scholar
[17]Korn, M. and Pak, I. (2003) Combinatorial evaluations of the Tutte polynomial. Preprint.Google Scholar
[18]Las Vergnas, M. (1983) Le polynôme de Martin d'un graphe Eulerien. Ann. Discrete Math. 17 397–411.Google Scholar
[19]Moffatt, I. (2008) Knot invariants and the Bollobás–Riordan polynomial of embedded graphs. European J. Combin. 29 95–107.Google Scholar
[20]Moffatt, I. (2013) Separability and the genus of a partial dual. European J. Combin. 34 355–378.Google Scholar
[21]Oxley, J. G. and Welsh, D. J. A. (1992) Tutte polynomials computable in polynomial time. Discrete Math. 109 185–192.Google Scholar
[22]Penrose, R. (1971) Applications of negative dimensional tensors. In Combinatorial Mathematics and its Applications (Welsh, D. J. A., ed.), Academic Press, pp. 221–244.Google Scholar
[23]Traldi, L. (2005) Parallel connections and coloured Tutte polynomials. Discrete Math. 290 291–299.CrossRefGoogle Scholar
[24]Wilson, S. E. (1979) Operators over regular maps. Pacific J. Math. 81 559–568.Google Scholar
[25]Woodall, D. R. (2002) Tutte polynomial expansions for 2-separable graphs. Discrete Math. 247 201–213.Google Scholar