Tutte polynomials and link polynomials

Author:
François Jaeger

Journal:
Proc. Amer. Math. Soc. **103** (1988), 647-654

MSC:
Primary 57M25; Secondary 05C10, 57M15

DOI:
https://doi.org/10.1090/S0002-9939-1988-0943099-0

MathSciNet review:
943099

Full-text PDF

Abstract | References | Similar Articles | Additional Information

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.

**[1]**K. Appel and W. Haken,*Supplement to: “Every planar map is four colorable. I. Discharging” (Illinois J. Math. 21 (1977), no. 3, 429–490) by Appel and Haken; “II. Reducibility” (ibid. 21 (1977), no. 3, 491–567) by Appel, Haken and J. Koch*, Illinois J. Math.**21**(1977), no. 3, 1–251. (microfiche supplement). MR**0543795****[2]**Rodney J. Baxter,*Exactly solved models in statistical mechanics*, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London, 1982. MR**690578****[3]**Claude Berge,*Graphes et hypergraphes*, Dunod, Paris-Brussels-Montreal, Que., 1973 (French). Deuxième édition; Collection Dunod Université, Série Violette, No. 604. MR**0357171****[4]**J. A. Bondy and U. S. R. Murty,*Graph theory with applications*, American Elsevier Publishing Co., Inc., New York, 1976. MR**0411988****[5]**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****[6]**J. R. Edmonds,*Pictures of knots and construction of planar triangulations*, Communication at the Third International Conference "Théorie des graphes et combinatoire," Marseille, June 1986.**[7]**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**, https://doi.org/10.1090/S0273-0979-1985-15361-3**[8]**Michael R. Garey and David S. Johnson,*Computers and intractability*, W. H. Freeman and Co., San Francisco, Calif., 1979. A guide to the theory of NP-completeness; A Series of Books in the Mathematical Sciences. MR**519066****[9]**Jim Hoste,*A polynomial invariant of knots and links*, Pacific J. Math.**124**(1986), no. 2, 295–320. MR**856165****[10]**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**, https://doi.org/10.1090/S0273-0979-1985-15304-2**[11]**V. F. R. Jones,*A new knot polynomial and von Neumann algebras*, Notices Amer. Math. Soc.**33**(1986), no. 2, 219–225. MR**830613****[12]**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****[13]**Louis H. Kauffman,*State models and the Jones polynomial*, Topology**26**(1987), no. 3, 395–407. MR**899057**, https://doi.org/10.1016/0040-9383(87)90009-7**[14]**-,*Statistical mechanics and the Jones polynomial*, preprint.**[15]**Louis H. Kauffman,*Formal knot theory*, Mathematical Notes, vol. 30, Princeton University Press, Princeton, NJ, 1983. MR**712133****[16]**Kunio Murasugi,*Jones polynomials and classical conjectures in knot theory*, Topology**26**(1987), no. 2, 187–194. MR**895570**, https://doi.org/10.1016/0040-9383(87)90058-9**[17]**Oystein Ore,*The four-color problem*, Pure and Applied Mathematics, Vol. 27, Academic Press, New York-London, 1967. MR**0216979****[18]**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**0498284**, https://doi.org/10.1098/rspa.1971.0067**[19]**Morwen B. Thistlethwaite,*A spanning tree expansion of the Jones polynomial*, Topology**26**(1987), no. 3, 297–309. MR**899051**, https://doi.org/10.1016/0040-9383(87)90003-6**[20]**W. T. Tutte,*A ring in graph theory*, Proc. Cambridge Philos. Soc.**43**(1947), 26–40. MR**0018406****[21]**W. T. Tutte,*A contribution to the theory of chromatic polynomials*, Canadian J. Math.**6**(1954), 80–91. MR**0061366**

Retrieve articles in *Proceedings of the American Mathematical Society*
with MSC:
57M25,
05C10,
57M15

Retrieve articles in all journals with MSC: 57M25, 05C10, 57M15

Additional Information

DOI:
https://doi.org/10.1090/S0002-9939-1988-0943099-0

Article copyright:
© Copyright 1988
American Mathematical Society