No Access

Efficient computation of the Kauffman bracket

Lauren Ellenberg

Arcadia University, 450 S Easton Road, Glenside, PA 19038, United States

Search for more papers by this author

Gabriella Newman

Google, 111 8th Avenue Google Chel-3, New York City, NY 10011-5202, USA

Search for more papers by this author

Stephen Sawin

Fairfield University, Fairfield, CT 06824, USA

Search for more papers by this author

, and

Jonathan Shi

Cornell University, Ithaca, NY 14853, USA

Search for more papers by this author

https://doi.org/10.1142/S0218216514500266Cited by:0 (Source: Crossref)

Abstract

This paper bounds the computational cost of computing the Kauffman bracket of a link in terms of the crossing number of that link. Specifically, it is shown that the image of a tangle with g boundary points and n crossings in the Kauffman bracket skein module is a linear combination of O(2^g) basis elements, with each coefficient a polynomial with at most n non-zero terms, each with integer coefficients, and that the link can be built one crossing at a time as a sequence of tangles with maximum number of boundary points bounded by for some C. From this it follows that the computation of the Kauffman bracket of the link takes time and memory a polynomial in n times .

Keywords:

AMSC: 57M27

References

D. Bar-Natan , Algebr. Geom. Topol. 2 , 337 ( 2002 ) . Crossref, Google Scholar
D. Bar-Natan, J. Knot Theory Ramifications 16(3), 243 (2007). Link, Web of Science, Google Scholar
G. Burde and H. Zieschang , Knots ( Walter de Gruyter , New York , 1986 ) . Google Scholar
H. Djidjev and I. Vrto, J. Graph Algorithms Appl. 7(3), 245 (2003). Crossref, Google Scholar
M. Freedmanet al., Quantum Topol. 1(2), 171 (2010). Crossref, Google Scholar
H. Gazit and G. L. Miller, Planar separators and the Euclidean norm, Int. Symp. Algorithms450, Lecture Notes in Computer Science (Springer, 1990) pp. 338–347. Google Scholar
L. H. Kauffman, An invariant of regular isotopy, announcement (1985), preprint (1986) . Google Scholar
T. Koshy , Catalan Numbers with Applications ( Oxford University Press , Oxford , 2009 ) . Google Scholar
K. Murasugi , Topology 26 , 187 ( 1987 ) . Crossref, Web of Science, Google Scholar
B. Trace , Proc. Amer. Math. Soc. 89 , 722 ( 1983 ) . Crossref, Web of Science, Google Scholar
V. G. Turaev , Quantum Invariants of Knots and 3-Manifolds , Studies in Mathematics ( Walter de Gruyter and Co. , Berlin , 1994 ) . Crossref, Google Scholar