Hostname: page-component-74656f9884-npj9w Total loading time: 0 Render date: 2026-11-09T17:51:16.863Z Has data issue: false hasContentIssue false
  • English
  • Français

Relative Tutte Polynomials for Coloured Graphs and Virtual Knot Theory

Published online by Cambridge University Press:  18 November 2009

Y. DIAO  and
G. HETYEI
Y. DIAO
Affiliation:
Department of Mathematics and Statistics, UNC Charlotte, Charlotte, NC 28223, USA (e-mail: ydiao@uncc.edu, ghetyei@uncc.edu)
G. HETYEI
Affiliation:
Department of Mathematics and Statistics, UNC Charlotte, Charlotte, NC 28223, USA (e-mail: ydiao@uncc.edu, ghetyei@uncc.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We introduce the concept of a relative Tutte polynomial of coloured graphs. We show that this relative Tutte polynomial can be computed in a way similar to the classical spanning tree expansion used by Tutte in his original paper on this subject. We then apply the relative Tutte polynomial to virtual knot theory. More specifically, we show that the Kauffman bracket polynomial (and hence the Jones polynomial) of a virtual knot can be computed from the relative Tutte polynomial of its face (Tait) graph with some suitable variable substitutions. Our method offers an alternative to the ribbon graph approach, using the face graph obtained from the virtual link diagram directly.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 19 , Issue 3 , May 2010 , pp. 343 - 369
Copyright
Copyright © Cambridge University Press 2009

References

[1]Bollobás, B. (1998) Modern Graph Theory, Graduate Texts in Mathematics, Springer.CrossRefGoogle Scholar
[2]Bollobás, B. and Riordan, O. (1999) A Tutte polynomial for coloured graphs. Combin. Probab. Comput. 8 45–93.CrossRefGoogle Scholar
[3]Bollobás, B. and Riordan, O. (2001) A polynomial of graphs on orientable surfaces. Proc. London Math. Soc. 83 513–531.CrossRefGoogle 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. (1971) A combinatorial model for series-parallel networks. Trans. Amer. Math. Soc. 154 1–22.CrossRefGoogle Scholar
[6]Brylawski, T. (1972) A decomposition for combinatorial geometries. Trans. Amer. Math. Soc. 171 235–282.CrossRefGoogle Scholar
[7]Chaiken, S. (1989) The Tutte polynomial of a ported matroid. J. Combin. Theory Ser. B 46 96–117.CrossRefGoogle Scholar
[8]Chmutov, S. Personal communication.Google Scholar
[9]Chmutov, S. (2009) Generalized duality for graphs on surfaces and the signed Bollobás–Riordan polynomial. J. Combin. Theory Ser. B 99 617–638.CrossRefGoogle Scholar
[10]Chmutov, S. and Pak, I. (2007) The Kauffman bracket of virtual links and the Bollobás–Riordan polynomial. Moscow Math. J. 7 409–418.CrossRefGoogle Scholar
[11]Chmutov, S. and Voltz, J. (2008) Thistlethwaite's theorem for virtual links. J. Knot Theory Ramification 17 1189–1198.CrossRefGoogle Scholar
[12]Diao, Y., Ernst, C. and Ziegler, U. (2009) Jones polynomial of knots formed by repeated tangle replacement operations. Topology Appl. 156 2226–2239.CrossRefGoogle Scholar
[13]Diao, Y., Hetyei, G. and Hinson, K. (2009) Tutte polynomials of tensor products of signed graphs and their applications in knot theory. J. Knot Theory Ramification 18 561–590.CrossRefGoogle Scholar
[14]Diao, Y., Hetyei, G. and Hinson, K. (2009) Invariants of composite networks arising as a tensor product. Graphs Combin. 25 273–290.CrossRefGoogle Scholar
[15]Ellis-Monaghan, J. A. and Traldi, L. (2006) Parametrized Tutte polynomials of graphs and matroids. Combin. Probab. Comput. 15 835–854.CrossRefGoogle Scholar
[16]Fortuin, C. M. and Kasteleyn, P. W. (1972) On the random-cluster model I: Introduction and relation to other models. Physica 57 536–564.CrossRefGoogle Scholar
[17]Jaeger, F., Vertigan, D. L. and Welsh, D. J. A. (1990) On the computational complexity of the Jones and Tutte polynomials. Math. Proc. Cambridge Phil. Soc. 108 35–53.CrossRefGoogle Scholar
[18]Kamada, N. (2002) On the Jones polynomials of checkerboard colorable virtual links. Osaka J. Math. 39 325–333.Google Scholar
[19]Kamada, N. (2004) Span of the Jones polynomial of an alternating virtual link. Algebraic & Geometric Topology 4 1083–1101.CrossRefGoogle Scholar
[20]Kauffman, L. H. (1989) A Tutte polynomial for signed graphs. Discrete Appl. Math. 25 105–127.CrossRefGoogle Scholar
[21]Kauffman, L. H. (1999) Virtual knot theory. Europ. J. Combin. 20 663–690.CrossRefGoogle Scholar
[22]Las Vergnas, M. (1977/78) Acyclic and totally cyclic orientations of combinatorial geometries. Discrete Math. 20 51–61.CrossRefGoogle Scholar
[23]Las Vergnas, M. (1981) Eulerian circuits of 4-valent graphs imbedded in surfaces. In Algebraic Methods in Graph Theory, Vol. I, II (Szeged 1978), Vol. 25 of Colloq. Math. Soc. János Bolyai, pp. 451–477.Google Scholar
[24]Las Vergnas, M. (1979) On Eulerian partitions of graphs. In Graph Theory and Combinatorics, Vol. 34 of Research Notes in Mathematics (Wilson, R. J., ed.), Pitman Advanced Publishing Program, pp. 62–75.Google Scholar
[25]Las Vergnas, M. (1984) The Tutte polynomial of a morphism of matroids II: Activities of orientations. In Progress in Graph Theory (Waterloo, Ont., 1982), Academic Press, pp. 367–380.Google Scholar
[26]Las Vergnas, M. (1999) The Tutte polynomial of a morphism of matroids I: Set-pointed matroids and matroid perspectives. Ann. Inst. Fourier 49 973–1015.CrossRefGoogle Scholar
[27]Thistlethwaite, M. B. (1987) A spanning tree expansion for the Jones polynomial. Topology 26 297–309.CrossRefGoogle Scholar
[28]Traldi, L. (2004) A subset expansion of the coloured Tutte polynomial. Combin. Probab. Comput. 13 269–275.CrossRefGoogle Scholar
[29]Tutte, W. T. (1954) A contribution to the theory of chromatic polynomials. Canad. J. Math. 6 80–91.CrossRefGoogle Scholar
[30]Welsh, D. J. A. (1976) Matroid Theory, Academic Press, London.Google Scholar