Jones polynomial of knots formed by repeated tangle replacement operations
type: Item
instance of: scholarly article
title: Jones polynomial of knots formed by repeated tangle replacement operations
zbMATH Open document ID: 1207.57010
author: Claus Ernst
author: U. Ziegler
author: Y. Diao
published in: Topology and its Applications
publication date: 2009-08-20T00:00:00Z
review text: 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 [\textit{F. Jaeger, D. L. Vertigan} and \textit{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.
reviewed by: Michael Heusener
Mathematics Subject Classification ID: 57M25
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5597567
zbMATH Keywords: Tutte polynomial
zbMATH Keywords: colored graphs
zbMATH Keywords: tensor product of graphs
zbMATH Keywords: 2-sum
zbMATH Keywords: tangles
zbMATH Keywords: knots
zbMATH Keywords: Jones polynomial
describes a project that uses: Knotscape
MaRDI profile type: Publication
full work available at URL: j.topol.2009.05.006
OpenAlex ID: W2087473174
cites work: An algorithm for the Tutte polynomials of graphs of bounded treewidth
cites work: Sampling large random knots in a confined space
cites work: A Tutte Polynomial for Coloured Graphs
cites work: The Tutte Polynomial Part I: General Theory
cites work: Q4012032
cites work: HAMILTONIAN CYCLES AND ROPE LENGTHS OF CONWAY ALGEBRAIC KNOTS
cites work: Numerical upper bounds on ropelengths of large physical knots
cites work: Q5477851
cites work: TUTTE POLYNOMIALS OF TENSOR PRODUCTS OF SIGNED GRAPHS AND THEIR APPLICATIONS IN KNOT THEORY
cites work: Invariants of composite networks arising as a tensor product
cites work: On the computational complexity of the Jones and Tutte polynomials
cites work: New Invariants in the Theory of Knots
cites work: A Tutte polynomial for signed graphs
cites work: Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width
cites work: COMPUTING THE JONES POLYNOMIAL ON BIPARTITE GRAPHS
cites work: Fast algorithms for computing Jones polynomials of certain links
cites work: Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width
cites work: Q3135082
cites work: Tutte polynomials computable in polynomial time
cites work: A spanning tree expansion of the Jones polynomial
cites work: Parallel connections and coloured Tutte polynomials
cites work: On the colored Tutte polynomial of a graph of bounded treewidth
cites work: A Contribution to the Theory of Chromatic Polynomials
DOI: 10.1016/J.TOPOL.2009.05.006
description: scientific article; zbMATH DE number 5597567