Algebraic number-theoretic properties of graph and matroid polynomials

Abstract

This thesis is an investigation into the algebraic number-theoretical properties of certain polynomial invariants of graphs and matroids. The bulk of the work concerns chromatic polynomials of graphs, and was motivated by two conjectures proposed during a 2008 Newton Institute workshop on combinatorics and statistical mechanics. The first of these predicts that, given any algebraic integer, there is some natural number such that the sum of the two is the zero of a chromatic polynomial (chromatic root); the second that every positive integer multiple of a chromatic root is also a chromatic root. We compute general formulae for the chromatic polynomials of two large families of graphs, and use these to provide partial proofs of each of these conjectures. We also investigate certain correspondences between the abstract structure of graphs and the splitting fields of their chromatic polynomials. The final chapter concerns the much more general multivariate Tutte polynomials—or Potts model partition functions—of matroids. We give three separate proofs that the Galois group of every such polynomial is a direct product of symmetric groups, and conjecture that an analogous result holds for the classical bivariate Tutte polynomial.