For each pair of algebraic numbers $(x,y)$, the complexity of computing the Tutte polynomial $T(G;x,y)$ of a planar graph $G$ is determined. This computation is found to be ...$\overline{\rm\#P}$-complete except when $(x-1)(y-1)=1,2$ or when $(x,y)$ is one of $(1,1)$, $(-1,-1)$, $(j,j^2)$, or $(j^2,j)$, where $j=e^{2\pi i/3}$, in which case it is polynomial time computable. A corollary gives the computational complexity of various enumeration problems for planar graphs.
Knots and physics Kauffman, Louis H
2001., 2001, 20010726, 2001-07-26, Letnik:
1
eBook
This invaluable book is an introduction to knot and link invariants as generalised amplitudes for a quasi-physical process. The demands of knot theory, coupled with a quantum-statistical framework, ...create a context that naturally and powerfully includes an extraordinary range of interrelated topics in topology and mathematical physics. The author takes a primarily combinatorial stance toward knot theory and its relations with these subjects. This stance has the advantage of providing direct access to the algebra and to the combinatorial topology, as well as physical ideas. The book is divided into two parts: Part I is a systematic course on knots and physics starting from the ground up, and Part II is a set of lectures on various topics related to Part I. Part II includes topics such as frictional properties of knots, relations with combinatorics, and knots in dynamical systems. In this third edition, a paper by the author entitled “Knot Theory and Functional Integration” has been added. This paper shows how the Kontsevich integral approach to the Vassiliev invariants is directly related to the perturbative expansion of Witten's functional integral. While the book supplies the background, this paper can be read independently as an introduction to quantum field theory and knot invariants and their relation to quantum gravity. As in the second edition, there is a selection of papers by the author at the end of the book. Numerous clarifying remarks have been added to the text.
We give a criterion to detect whether the derivatives of knot polynomials at a point are Vassiliev invariants or not. As an application we show that for each nonnegative integer n, JK(n)(a) is a ...Vassiliev invariant if and only if a=1, where JK(n)(a) is the nth derivative of the Jones polynomial JK(t) of a knot K at t=a. Similarly we apply the criterion for the Conway, Alexander, Q-, HOMFLY and Kauffman polynomial.
Also we give two methods of constructing a polynomial invariant from a numerical Vassiliev invariant of degree n, by using a sequence of knots induced from a double dating tangle. These two new polynomial invariants are Vassiliev invariants of degree ⩽n and their values on a knot are also polynomials of degree ⩽n.
Chern-Simons gauge theory, since its inception as a topological quantum field theory, has proved to be a rich source of understanding for knot invariants. In this work the theory is used to explore ...the definition of the expectation value of a network of Wilson lines — an embedded graph invariant. Using a generalization of the variational method, lowest-order results for invariants for graphs of arbitrary valence and general vertex tangent space structure are derived. Gauge invariant operators are introduced. Higher order results are found. The method used here provides a Vassiliev-type definition of graph invariants which depend on both the embedding of the graph and the group structure of the gauge theory. It is found that one need not frame individual vertices. However, without a global projection of the graph there is an ambiguity in the relation of the decomposition of distinct vertices. It is suggested that framing may be seen as arising from this ambiguity — as a way of relating frames at distinct vertices.
New points of view in knot theory
Bulletin (new series) of the American Mathematical Society/Bulletin, new series, of the American Mathematical Society,
04/1993
Journal Article
PDF
