Tutte chromatic identities from the Temperley–Lieb algebra

Fendley, Paul¹ ; Krushkal, Vyacheslav²

¹ All Souls College and the Rudolf Peierls Centre for Theoretical Physics, University of Oxford, 1 Keble Road, Oxford OX13NP, UK
² Department of Mathematics, University of Virginia, Charlottesville, VA 22904-4137, USA

Geometry & topology, Tome 13 (2009) no. 2, pp. 709-741.

Résumé

This paper introduces a conceptual framework, in the context of quantum topology and the algebras underlying it, for analyzing relations obeyed by the chromatic polynomial $\chi \left(Q\right)$ of planar graphs. Using it we give new proofs and substantially extend a number of classical results concerning the combinatorics of the chromatic polynomial. In particular, we show that Tutte’s golden identity is a consequence of level-rank duality for $SO\left(N\right)$ topological quantum field theories and Birman–Murakami–Wenzl algebras. This identity is a remarkable feature of the chromatic polynomial relating $\chi \left(\varphi +2\right)$ for any triangulation of the sphere to ${\left(\chi \left(\varphi +1\right)\right)}^2$ for the same graph, where $\varphi$ denotes the golden ratio. The new viewpoint presented here explains that Tutte’s identity is special to these values of the parameter $Q$. A natural context for analyzing such properties of the chromatic polynomial is provided by the chromatic algebra, whose Markov trace is the chromatic polynomial of an associated graph. We use it to show that another identity of Tutte’s for the chromatic polynomial at $Q=\varphi +1$ arises from a Jones–Wenzl projector in the Temperley–Lieb algebra. We generalize this identity to each value $Q=2+2cos\left(2\pi j∕\left(n+1\right)\right)$ for $j<n$ positive integers. When $j=1$, these $Q$ are the Beraha numbers, where the existence of such identities was conjectured by Tutte. We present a recursive formula for this sequence of chromatic polynomial relations.

Détail

DOI : 10.2140/gt.2009.13.709

Keywords: chromatic polynomial, Temperley–Lieb algebra, level-rank duality, Tutte golden identity, planar graph, Beraha number

Bibliographie

[1] D Bar-Natan, \ttdbnsymb (2008)

[2] S. Beraha, Infinite nontrivial families of maps and chromials, PhD thesis, Johns Hopkins University (1975)

[3] J S Birman, H Wenzl, Braids, link polynomials and a new algebra, Trans. Amer. Math. Soc. 313 (1989) 249

[4] B Bollobás, Modern graph theory, Graduate Texts in Math. 184, Springer (1998)

[5] P Fendley, Topological order from quantum loops and nets, Annals of Physics 323 (2008) 3113

[6] P Fendley, V Krushkal, Link invariants, the chromatic polynomial and the Potts model

[7] P Fendley, N Read, Exact $S$–matrices for supersymmetric sigma models and the Potts model, J. Phys. A 35 (2002) 10675

[8] L. Fidkowski, M H. Freedman, C. Nayak, K. Walker, Z. Wang, From string nets to nonabelions

[9] M H Freedman, A magnetic model with a possible Chern–Simons phase, Comm. Math. Phys. 234 (2003) 129

[10] F Jaeger, On some graph invariants related to the Kauffman polynomial, from: "Progress in knot theory and related topics", Travaux en Cours 56, Hermann (1997) 69

[11] V F R. Jones, Planar algebras

[12] V F R Jones, Index for subfactors, Invent. Math. 72 (1983) 1

[13] L H Kauffman, S L Lins, Temperley–Lieb recoupling theory and invariants of $3$–manifolds, Annals of Math. Studies 134, Princeton University Press (1994)

[14] L Kauffmann, H Saleur, An algebraic approach to the planar coloring problem, Comm. Math. Phys. 152 (1993) 565

[15] G Kuperberg, Spiders for rank $2$ Lie algebras, Comm. Math. Phys. 180 (1996) 109

[16] P Martin, D Woodcock, The partition algebras and a new deformation of the Schur algebras, J. Algebra 203 (1998) 91

[17] E J Mlawer, S G Naculich, H A Riggs, H J Schnitzer, Group-level duality of WZW fusion coefficients and Chern–Simons link observables, Nuclear Phys. B 352 (1991) 863

[18] J Murakami, The Kauffman polynomial of links and representation theory, Osaka J. Math. 24 (1987) 745

[19] R Penrose, Applications of negative dimensional tensors, from: "Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969)", Academic Press (1971) 221

[20] H Saleur, Zeroes of chromatic polynomials: a new approach to Beraha conjecture using quantum groups, Comm. Math. Phys. 132 (1990) 657

[21] H N V Temperley, 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) 251

[22] W T Tutte, More about chromatic polynomials and the golden ratio, from: "Combinatorial Structures and their Applications (Proc. Calgary Internat. Conf., 1969)", Gordon and Breach (1970) 439

[23] W T Tutte, On chromatic polynomials and the golden ratio, J. Combinatorial Theory 9 (1970) 289

[24] W T Tutte, Graph theory as I have known it, Oxford Lecture Ser. in Math. and its Appl. 11, The Clarendon Press, Oxford University Press (1998)

[25] K Walker, On Witten's $3$–manifold invariants

[26] K Walker, Talk given at IPAM conference “Topological Quantum Computing”, (2007)

[27] H Wenzl, On sequences of projections, C. R. Math. Rep. Acad. Sci. Canada 9 (1987) 5

[28] E Witten, Quantum field theory and the Jones polynomial, Comm. Math. Phys. 121 (1989) 351

[29] S Yamada, An operator on regular isotopy invariants of link diagrams, Topology 28 (1989) 369