Algebraic methods for chromatic polynomials Philipp Augustin Reinfeld London School of Economies and Politicai Science Ph.D. 2 Abstract: The chromatic polynomials of certain families of graphs can be calcu- lai ed by a transfer matrix method. The transfer matrix commutes with an action of the symmetric group on the colours. Using représentation theory, it is shown that the matrix is équivalent to a block-diagonal matrix. The multiplicities and the sizes of the blocks are obtained. Using a repeated inclusion-exclusion argument the entries of the blocks can be calculated. In particular, from one of the inclusion-exclusion arguments it follows that the transfer matrix can be written as a linear combination of operators which, in certain cases, form an algebra. The eigenvalues of the blocks can be inferred from this structure. The form of the chromatic polynomials permits the use of a theorem by Beraha, Kahane and Weiss to determine the limiting behaviour of the roots. The theorem says that, apart from some isolated points, the roots approach certain curves in the complex piane. Some improvements have been made in the methods of calculating these curves. Many examples are discussed in détail. In particular the chromatic polynomials of the family of the so-called generalized dodecahedra and four similar families of cubic graphs are obtained, and the limiting behaviour of their roots is discussed. Contents 1 Introduction 11 1.1 Overview 11 2 Modules and colourings 14 2.1 Some représentation theory 14 2.2 The symmetric group 17 2.3 The module of colourings V {B) 24 k 2.4 The irreducible submodules of V (B) 27 k 2.4.1 The complété graph case 29 2.4.2 A change of basis 32 2.4.3 The général case 34 2.5 Examples 34 2.6 A new module 40 3 The compatibility matrix method 44 3.1 Bracelets 44 3.2 The compatibility matrix method 47 3.3 Décomposition of the compatibility matrix 49 3 CONTENTS 4 3.4 Réduction to the complété base graph 52 3.5 The S m opérât ors 54 3.6 Change of basis 57 3.7 Action of S m (&) on the irreducible submodules of Vk{b) 59 3.8 Examples 64 3.9 Summary 75 4 Explicit calculations of chromatic poiynomials 79 4.1 A catalogue of U^ 80 4.1.1 The case b > 3 and d = 3 81 4.1.2 The case b = 3 and d > 3 83 4.2 Two Examples 85 4.3 Permutations of the vertex sets 89 4.4 Réduction of base graphs 90 4.5 Generalised dodecahedra 92 4.6 Four more families of cubic graphs 100 4.6.1 The family (468) 102 n 4.6.2 The family (477) 106 n 4.6.3 The family (567) 110 n 4.6.4 The family (666) 114 n 5 Equimodular curves 119 5.1 A theorem of Beraha, Kahane and Weiss 120 5.2 Equimodular points 122 CONTENTS 5 5.3 The résultant 123 5.4 Equimodular curves 125 5.4.1 Examples 127 5.5 Dominance 129 5.6 Numerical computations 131 5.6.1 The path of length three with the identity linking set . .. . 132 5.6.2 Generalised dodecahedra 136 5.6.3 The family (468) 138 n 5.6.4 The family (477) 140 n 5.6.5 The family (567) 142 n 5.6.6 The family (666) 144 n 6 The operator algebras and 146 6.1 A binary opération for matchings 147 6.2 The operator algebra Ab{k) 147 6.3 A minimal generating set 149 6.4 The operator algebra A^ik) 152 6.5 The level b — 1 for the identity linking set 155 A Newton's formula 164 B The H-sériés catalogue 165 C The reduced matrices for level 2 173 CONTENTS 6 D Maple programs 177 D.l The program EquiDominantPoints 177 D.2 The program DomTest 179 D.3 The program Slices 180 List of Tables 2.1 Summary of Example 2.10 39 4.1 The induced graphs \n\(Lniji)\'R.\ in case of the family D 93 i i j n 4.2 The graphs of the H-series 94 4.3 The graphs of the #*-series 95 4.4 The induced graphs (£7^,7^)17^1 in case of the family (468) . . . 103 n 4.5 The induced graphs (-^,7^)17^1 in case of the family (477)„ . . . 107 4.6 The induced graphs 17^1 (1^,7^)17^1 in case of the family (567) . . . Ili n 4.7 The induced graphs ^(L-jz^n^i7^1 in case of the family (666) . . . 115 n 6.1 The matrices Ufo , Ufo and Ufo in the case b — 3 154 7 For Amalia, who left too early. 8 Acknowledgements First of all, I would like to thank Norman Biggs for being such a excellent Super- visor. He has supported, guided and encouraged me, and he has also kept my feet on the ground when it was necessary. I am very grateful for his time and patience throughout my PhD. Next I would like to thank the rest of the department. In particular Jan van den Heuvel, Mark Baltovic, Jackie Everid and David Scott for always having an open ear and good advice. Thanks also to Robert Shrock, of Stony Brook University, New York, for finding the time and the financial support for me to visit and work with him. I am indebted to the UK Engineering and Physical Sciences Research Council (EP- SRC) , the London School of Economies and Politicai Science and the Department of Mat hématies for financial assistance throughout my PhD. My parents have also been a source of moral and financial support throughout my studies. They have always given my sisters and myself unconditional support and the security and warmth of a true family. I must also thank Maria del Mar for her most wonderful support, patience and understanding over the last three years. Finally I would like to finish by praising the European Union for providing a frame- work and some financial support for my studies abroad. In particular I have to thank the English university system for its openness and flexibility: recognizing my German high school degree and allowing me to study in England; covering my tuition fees; fully validating my year of studies in Italy; and ali with a minimal amount of bureaucracy. I hope that this openness and flexibility becomes common practice throughout the European Union. 9 Statement of originality Most of the work presented in this thesis is a continuation of work by N.L. Biggs [5], [8], [7], [9], [4] and [6]. The work appearing in this thesis is entirely my own except where stated otherwise. In particular: • The observation that the compatibility matrix commutes with the action of the symmetric group has also been exploited by M.H. Klin and C. Pech; see [9]. • The Examples 3.7, 3.8 and 3.9 have been published in [9]. They are due to me. • The chromatic polynomial for the generalised dodecahedron was obtained by S.C. Chang [11]. Here, the polynomial is calculaied in a différent way, to illustrâte the compatibility matrix method. • The Lemmas 6.12, 6.14 and Corollaries 6.13 and 6.15 are joint work with Jan van den Heuvel. 10