JOURNAL OF
ALGEBRAIC
COMBINATORICS

Home > Vol 4, No 2 (1995)

François Jaeger

Motivated by the construction of invariants of links in 3-space, we study spin models on graphs for which all edge weights (considered as matrices) belong to the Bose-Mesner algebra of some association scheme. We show that for series-parallel graphs the computation of the partition function can be performed by using series-parallel reductions of the graph appropriately coupled with operations in the Bose-Mesner algebra. Then we extend this approach to all plane graphs by introducing star-triangle transformations and restricting our attention to a special class of Bose-Mesner algebras which we call exactly triply regular. We also introduce the following two properties for Bose-Mesner algebras. The planar duality property (defined in the self-dual case) expresses the partition function for any plane graph in terms of the partition function for its dual graph, and the planar reversibility property asserts that the partition function for any plane graph is equal to the partition function for the oppositely oriented graph. Both properties hold for any Bose-Mesner algebra if one considers only series-parallel graphs instead of arbitrary plane graphs. We relate these notions to spin models for link invariants, and among other results we show that the Abelian group Bose-Mesner algebras have the planar duality property and that for self-dual Bose-Mesner algebras, planar duality implies planar reversibility. We also prove that for exactly triply regular Bose-Mesner algebras, to check one of the above properties it is sufficient to check it on the complete graph on four vertices. A number of applications, examples and open problems are discussed.

1. E. Bannai, "Association schemes and fusion algebras (An introduction)," J. ofAlg. Comb. 2 (1993), 327-344.
2. E. Bannai and E. Bannai, "Generalized generalized spin models (four-weight spin models)," Pacific J. Math., to appear.
3. E. Bannai and E. Bannai, "Spin models on finite cyclic groups," J. ofAlg. Comb. 3 (1994), 243-259.
4. E. Bannai and E. Bannai, "Generalized spin models and association schemes," Mem. Fac. Sci. Kyushu Univ. Ser. A, vol. 47 (1993), 397-409.
5. E. Bannai, E. Bannai, T. Ikuta, and K. Kawagoe, "Spin models constructed from the Hamming association schemes H(d, q)," Proceedings Wth Algebraic Combinatorics Symposium, Gifu, 1992, pp. 91-106.
6. E. Bannai, E. Bannai, and F. Jaeger, "On spin models, modular invariance, and duality," submitted.
7. A.E. Brouwer, A.M. Cohen, and A. Neumaier, "Distance-regular graphs," Springer-Verlag, Ergebnisse der Mathematik und ihrer Grenzgebiete,
3. Folge, Band 18, 1989.
8. E. Bannai and T. Ito, Algebraic Combinatorics I, Association schemes, Benjamin/Cummings, Menlo Park, 1984.
9. E. Bannai, F. Jaeger, and A. Sail, "Classification of small spin models," Kyushu J. of Math. vol. 48, no. 1 (1994), 185-200.
10. R.C. Bose and D.M. Mesner, "On linear associative algebras corresponding to association schemes of partially balanced designs," Ann. Math. Statist. 30 (1959), 21-38.
11. G. Burde and H. Zieschang, Knots, de Gruyter, Berlin, New York, 1985.
12. R.J. Baxter, Exactly solved models in statistical mechanics, Academic Press, 1982.
13. A. Berman, "Skew Hadamard matrices of order 16," in: Theory and Practice of Combinatorics, A. Rosa, G. Sabidussi, J. Turgeon editors, Annals of Discrete Math. 12, North Holland, 1982,45-47.
14. N.L. Biggs, "Interaction models," London Math. Soc. Lecture Notes 30, Cambridge University Press, 1977.
15. N.L. Biggs, "Algebraic Graph Theory," Cambridge Tracts in Math. 67, Cambridge University Press, 1974.
16. N.L. Biggs, "On the duality of interaction models," Math. Proc. Cambridge Philos. Soc. 80 (1976), 429-436.
17. P.J. Cameron, J.M. Goethals, and J.J. Seidel, "The Krein condition, spherical designs, Norton algebras and permutation groups," Kon. Nederl. Akad. Wet. Proc. Ser. A81 (1978) 2, 196-206.
18. P.J. Cameron, J.M. Goethals, and J.J. Seidel, "Strongly regular graphs having strongly regular subconstituents," /. Algebra 55 (1978), 257-280.
19. C.J. Colbourn, J.S. Provan, and D. Vertigan, "A new approach to solving three combinatorial enumeration problems on planar graphs," University of North Carolina at Chapel Hill, technical report UNC/OR/TR92-19, 1992.
20. P. Delsarte, "An algebraic approach to the association schemes of coding theory," Phillips Research Reports Supplements 10 (1973).
21. R.J. Duffin, "Topology of series-parallel networks," / Math. Anal. Appl. 10 (1965), 303-318.
22. G.V. Epifanov, "Reduction of a plane graph to an edge by a star-triangle transformation," Soviet Math. Doklady 7(1966), 13-17.
23. T. A. Feo and J. S. Provan, "Delta-wye transformations and the efficient reduction of two-terminal planar graphs," Operations Research 41 (1993) 3, 572-582.
24. B. Griinbaum, Convex Polytopes, Interscience Publishers, London, 1967.
25. D. M. Goldschmidt and V. F. R. Jones, "Metaplectic link invariants," Geom. Dedicata 31 (1989), 165-191.
26. P. de la Harpe, "Spin models for link polynomials, strongly regular graphs and Jaeger's Higman-Sims model," Pacific J. of Math. 162 (1994), 57-96.
27. P. de la Harpe and F. Jaeger, "Chromatic invariants for finite graphs: theme and polynomial variations,"