On Tutte’s chromatic invariant
HTML articles powered by AMS MathViewer
- by Sabin Cautis and David M. Jackson PDF
- Trans. Amer. Math. Soc. 362 (2010), 491-507 Request permission
Abstract:
Consider a simple connected graph $\mathsf {G}$ embedded in the plane together with a contractible circuit $\mathsf {J}$. For a partition $\phi$ of the vertex set of $\mathsf {J}$ we denote by $P_{(\mathsf {G},\phi )}(t)$ the number of ways of assigning one of $t$ given colours to each vertex of $\mathsf {G}$ so that vertices in the same block of $\phi$ have the same colour. Tutte showed that this polynomial may be expressed uniquely as a linear combination of $P_{(\mathsf {G},\pi )}(t)$ over all planar partitions $\pi$ of $\mathsf {J}$, with scalars $\vartheta _{\phi ,\pi }(t)$ that are independent of $\mathsf {G}$. We show that the (chromatic) invariants $\vartheta _{\phi ,\pi }$ have a natural algebraic setting in terms of the orthogonal projection from the partition algebra $\mathbb {P}_r(t)$ to the Temperley-Lieb subalgebra $\mathbb {TL}_r(t,1)$. We define the genus of a partition and give an extension of the invariants to arbitrary genus $g$. Finally, we summarise the rôle of the genus $0$ invariants in the algebraic approach of Birkhoff and Lewis to the Four Colour Theorem.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
- K. Appel, W. Haken, and J. Koch, Every planar map is four colorable. II. Reducibility, Illinois J. Math. 21 (1977), no. 3, 491–567. MR 543793
- G. D. Birkhoff and D. C. Lewis, Chromatic polynomials, Trans. Amer. Math. Soc. 60 (1946), 355–451. MR 18401, DOI 10.1090/S0002-9947-1946-0018401-4
- S. Cautis and D. M. Jackson, The matrix of chromatic joins and the Temperley-Lieb algebra, J. Combin. Theory Ser. B 89 (2003), no. 1, 109–155. MR 1999738, DOI 10.1016/S0095-8956(03)00071-6
- Louis H. Kauffman, Statistical mechanics and the Jones polynomial, Braids (Santa Cruz, CA, 1986) Contemp. Math., vol. 78, Amer. Math. Soc., Providence, RI, 1988, pp. 263–297. MR 975085, DOI 10.1090/conm/078/975085
- L. Kauffman and R. Thomas, Temperley-Lieb algebras and the Four Colour Theorem. Available at http://math.uic.edu/$\sim$kauffman/TLFCT.pdf.
- Tom Halverson and Arun Ram, Partition algebras, European J. Combin. 26 (2005), no. 6, 869–921. MR 2143201, DOI 10.1016/j.ejc.2004.06.005
- V. F. R. Jones, Planar Algebras, I. http://xxx.lanl.gov/abs/math/9909027.
- Paul Martin, Potts models and related problems in statistical mechanics, Series on Advances in Statistical Mechanics, vol. 5, World Scientific Publishing Co., Inc., Teaneck, NJ, 1991. MR 1103994, DOI 10.1142/0983
- Neil Robertson, Daniel Sanders, Paul Seymour, and Robin Thomas, The four-colour theorem, J. Combin. Theory Ser. B 70 (1997), no. 1, 2–44. MR 1441258, DOI 10.1006/jctb.1997.1750
- Richard P. Stanley, Enumerative combinatorics. Vol. 1, Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, Cambridge, 1997. With a foreword by Gian-Carlo Rota; Corrected reprint of the 1986 original. MR 1442260, DOI 10.1017/CBO9780511805967
- Private communication per J. Geelen, December 2004.
- W. T. Tutte, On the Birkhoff-Lewis equations, Discrete Math. 92 (1991), no. 1-3, 417–425. MR 1140602, DOI 10.1016/0012-365X(91)90296-E
- W. T. Tutte, The matrix of chromatic joins, J. Combin. Theory Ser. B 57 (1993), no. 2, 269–288. MR 1207492, DOI 10.1006/jctb.1993.1021
Additional Information
- Sabin Cautis
- Affiliation: Department of Mathematics, Rice University, Houston, Texas 77251
- MR Author ID: 712430
- Email: scautis@math.harvard.edu
- David M. Jackson
- Affiliation: Department of Combinatorics and Optimization, University of Waterloo, Ontario, Canada N2L 3G1
- MR Author ID: 92555
- Email: dmjackson@math.uwaterloo.ca
- Received by editor(s): February 1, 2006
- Received by editor(s) in revised form: July 11, 2007, and May 9, 2008
- Published electronically: August 18, 2009
- © Copyright 2009 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 362 (2010), 491-507
- MSC (2000): Primary 05C15
- DOI: https://doi.org/10.1090/S0002-9947-09-04836-3
- MathSciNet review: 2550161