Tutte polynomials and link polynomials

Jaeger, François

doi:10.1090/S0002-9939-1988-0943099-0

Tutte polynomials and link polynomials
HTML articles powered by AMS MathViewer

by François Jaeger PDF

Proc. Amer. Math. Soc. 103 (1988), 647-654 Request permission

Abstract:

We show how the Tutte polynomial of a plane graph can be evaluated as the "homfly" polynomial of an associated oriented link. Then we discuss some consequences for the partition function of the Potts model, the Four Color Problem and the time complexity of the computation of the homfly polynomial.

References

K. Appel and W. Haken, Every planar map is four colorable. I. Discharging, Illinois J. Math. 21 (1977), no. 3, 429–490. MR 543792
Rodney J. Baxter, Exactly solved models in statistical mechanics, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London, 1982. MR 690578
Claude Berge, Graphes et hypergraphes, Collection Dunod Université, Série Violette, No. 604, Dunod, Paris-Brussels-Montreal, Que., 1973 (French). Deuxième édition. MR 0357171
J. A. Bondy and U. S. R. Murty, Graph theory with applications, American Elsevier Publishing Co., Inc., New York, 1976. MR 0411988
J. H. Conway, An enumeration of knots and links, and some of their algebraic properties, Computational Problems in Abstract Algebra (Proc. Conf., Oxford, 1967) Pergamon, Oxford, 1970, pp. 329–358. MR 0258014

Pictures of knots and construction of planar triangulations

P. Freyd, D. Yetter, J. Hoste, W. B. R. Lickorish, K. Millett, and A. Ocneanu, A new polynomial invariant of knots and links, Bull. Amer. Math. Soc. (N.S.) 12 (1985), no. 2, 239–246. MR 776477, DOI 10.1090/S0273-0979-1985-15361-3
Michael R. Garey and David S. Johnson, Computers and intractability, A Series of Books in the Mathematical Sciences, W. H. Freeman and Co., San Francisco, Calif., 1979. A guide to the theory of NP-completeness. MR 519066
Jim Hoste, A polynomial invariant of knots and links, Pacific J. Math. 124 (1986), no. 2, 295–320. MR 856165
Vaughan F. R. Jones, A polynomial invariant for knots via von Neumann algebras, Bull. Amer. Math. Soc. (N.S.) 12 (1985), no. 1, 103–111. MR 766964, DOI 10.1090/S0273-0979-1985-15304-2
V. F. R. Jones, A new knot polynomial and von Neumann algebras, Notices Amer. Math. Soc. 33 (1986), no. 2, 219–225. MR 830613
Louis H. Kauffman, New invariants in the theory of knots, Astérisque 163-164 (1988), 6, 137–219, 282 (1989) (English, with French summary). On the geometry of differentiable manifolds (Rome, 1986). MR 999974
Louis H. Kauffman, State models and the Jones polynomial, Topology 26 (1987), no. 3, 395–407. MR 899057, DOI 10.1016/0040-9383(87)90009-7

Statistical mechanics and the Jones polynomial

Louis H. Kauffman, Formal knot theory, Mathematical Notes, vol. 30, Princeton University Press, Princeton, NJ, 1983. MR 712133
Kunio Murasugi, Jones polynomials and classical conjectures in knot theory, Topology 26 (1987), no. 2, 187–194. MR 895570, DOI 10.1016/0040-9383(87)90058-9
Oystein Ore, The four-color problem, Pure and Applied Mathematics, Vol. 27, Academic Press, New York-London, 1967. MR 0216979
H. N. V. Temperley and E. H. Lieb, Relations between the “percolation” and “colouring” problem and other graph-theoretical problems associated with regular planar lattices: some exact results for the “percolation” problem, Proc. Roy. Soc. London Ser. A 322 (1971), no. 1549, 251–280. MR 498284, DOI 10.1098/rspa.1971.0067
Morwen B. Thistlethwaite, A spanning tree expansion of the Jones polynomial, Topology 26 (1987), no. 3, 297–309. MR 899051, DOI 10.1016/0040-9383(87)90003-6
W. T. Tutte, A ring in graph theory, Proc. Cambridge Philos. Soc. 43 (1947), 26–40. MR 18406, DOI 10.1017/s0305004100023173
W. T. Tutte, A contribution to the theory of chromatic polynomials, Canad. J. Math. 6 (1954), 80–91. MR 61366, DOI 10.4153/cjm-1954-010-9