×

Jones polynomial of knots formed by repeated tangle replacement operations. (English) Zbl 1207.57010

The paper under discussion deals with the computational complexity theory of the Jones polynomial of knots and links in the three dimensional sphere. It is known that the computation of the Jones polynomial of an alternating link is \(\#P\)-hard [F. Jaeger, D. L. Vertigan and D. J. A. Welsh, Math. Proc. Camb. Philos. Soc. 108, No. 1, 35–53 (1990; Zbl 0747.57006)].
The authors construct a large family of knots by tangle replacement operations starting with a simple diagram \(D_0\). Let \(k\) be a constant and suppose that \(D_m\) is an \(n\)-crossing diagram obtained from a simple diagram \(D_0\) by \(m\) tangle replacement operations involving the tangles \(\Gamma_1,\dots,\Gamma_{m}\). The main result of the paper is that the Jones polynomial of \(D_{m}\) can be computed in time \(O(n^{k})\) if \(D_0\) and all the tangles \(\Gamma_1,\dots,\Gamma_{m}\) have at most \(k\) crossings. A consequence is that the Jones polynomial of an \(n\)-crossing Montesinos link can be computed in \(O(n^2)\) time.

MSC:

57M25 Knots and links in the \(3\)-sphere (MSC2010)
68Q25 Analysis of algorithms and problem complexity

Citations:

Zbl 0747.57006

Software:

Knotscape
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Andrzejak, A., An algorithm for the Tutte polynomials of graphs of bounded treewidth, Discrete Math., 190, 1-3, 39-54 (1998) · Zbl 0955.05101
[2] Arsuaga, J.; Diao, Y.; Hinson, K.; Karadayi, E.; Saito, M., Sampling large random knots in a confined space, J. Phys. A, 40, 11697-11711 (2007) · Zbl 1133.57004
[3] Bar-Natan, D.; Morrison, S., KnotTheory package, available at
[4] Bollobás, B.; Riordan, O., A Tutte polynomial for coloured graph, Combin. Probab. Comput., 8, 45-93 (1999) · Zbl 0926.05017
[5] F. Bonahon, L. Siebenmann, Geometric splittings of knots and Conway’s algebraic knots, unpublished manuscript, 1980; F. Bonahon, L. Siebenmann, Geometric splittings of knots and Conway’s algebraic knots, unpublished manuscript, 1980
[6] Brylawski, T., The Tutte polynomial I: General theory, (Barlotti, A., Matroid Theory and Its Applications (1982), Liguori Editore, S.r.I), 125-275 · Zbl 1302.05023
[7] Brylawski, T.; Oxley, J. G., The Tutte polynomial and its applications, (White, N., Matroid Applications (1992), Cambridge University Press), 123-225 · Zbl 0769.05026
[8] Diao, Y.; Ernst, C., Hamiltonian cycles and ropelengths of Conway algebraic knots, J. Knot Theory Ramifications, 15, 121-142 (2006) · Zbl 1088.57005
[9] Diao, Y.; Ernst, C.; Kavuluru, R.; Ziegler, U., Numerical upper bounds on ropelengths of large physical knots, J. Phys. A, 39, 4829-4843 (2006) · Zbl 1092.57004
[10] Diao, Y.; Ernst, C.; Ziegler, U., Generating large random link diagrams, (Calvo, J. A.; Millett, K. C.; Rawdon, E. J.; Stasiak, A., Physical and Numerical Models in Knot Theory Including Applications to the Life Sciences (2005), World Scientific Publishing: World Scientific Publishing Singapore), 473-494 · Zbl 1106.57005
[11] Y. Diao, G. Hetyei, K. Hinson, Tutte polynomials of tensor products of signed graphs and their applications in knot theory, J. Knot Theory Ramifications, in press; Y. Diao, G. Hetyei, K. Hinson, Tutte polynomials of tensor products of signed graphs and their applications in knot theory, J. Knot Theory Ramifications, in press · Zbl 1185.05083
[12] Y. Diao, G. Hetyei, K. Hinson, Invariants of composite networks arising as a tensor product, Graphs Combin., in press; Y. Diao, G. Hetyei, K. Hinson, Invariants of composite networks arising as a tensor product, Graphs Combin., in press · Zbl 1221.05134
[13] Hara, M.; Tani, S.; Yamamoto, M., A polynomial-time algorithm for computing the Jones polynomials of arborescent links, Inf. Technol. Lett., 1, 16-17 (2002), (in Japanese)
[14] Hoste, J.; Thistlethwaite, M., Knotscape, available at
[15] Jaeger, F.; Vertigan, D. L.; Welsh, D. J.A., On the computational complexity of the Jones and Tutte polynomials, Math. Proc. Cambridge Philos. Soc., 108, 35-53 (1990) · Zbl 0747.57006
[16] Kauffman, L. H., New invariants in the theory of knots, Amer. Math. Monthly, 95, 3, 195-242 (1988) · Zbl 0657.57001
[17] Kauffman, L. H., A Tutte polynomial for signed graphs, Discrete Appl. Math., 25, 105-127 (1989) · Zbl 0698.05026
[18] Makowsky, J. A., Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width, Discrete Appl. Math., 145, 276-290 (2005) · Zbl 1084.05505
[19] J. Mighton, Knot theory on bipartite graphs, PhD thesis, Dept. of Math., University of Toronto, Canada, 1999; J. Mighton, Knot theory on bipartite graphs, PhD thesis, Dept. of Math., University of Toronto, Canada, 1999 · Zbl 0998.57026
[20] Murakamia, M.; Harab, M.; Yamamotoc, M.; Tani, S., Fast algorithms for computing Jones polynomials of certain links, Theoret. Comput. Sci., 374, 1-24 (2007) · Zbl 1162.57302
[21] Noble, S., Evaluating the Tutte polynomial for graphs of bounded tree-width, Combin. Probab. Comput., 7, 3, 307-321 (1998) · Zbl 0917.05072
[22] Oxley, J. G., Matroid Theory (1992), Oxford University Press: Oxford University Press Oxford · Zbl 0784.05002
[23] Oxley, J. G.; Welsh, D. J.A., Tutte polynomials computable in polynomial time, Discrete Math., 109, 185-192 (1992) · Zbl 0780.05011
[24] Thistlethwaite, M. B., A spanning tree expansion for the Jones polynomial, Topology, 26, 3, 297-309 (1987) · Zbl 0622.57003
[25] Traldi, L., Parallel connections and coloured Tutte polynomials, Discrete Math., 290, 291-299 (2005) · Zbl 1069.05021
[26] Traldi, L., On the colored Tutte polynomial of a graph of bounded treewidth, Discrete Appl. Math., 154, 1032-1036 (2006) · Zbl 1091.05027
[27] Tutte, W. T., A contribution to the theory of chromatic polynomials, Canad. J. Math., 6, 80-91 (1954) · Zbl 0055.17101
[28] Utsumi, T.; Imai, K., Computation of the Jones polynomials for pretzel links, IPSJ SIG Tech. Rep., 085, 43-48 (2002), (in Japanese)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.