Graph Complexity and Mahler Measure

Dan Silver (South Alabama)

Abstract: In this joint work with Susan G. Williams we define the (torsion) complexity of a finite edge-weighted graph to be the order of the torsion subgroup of the abelian group presented by its Laplacian matrix. When G is d-periodic (i.e., G has a free $Z^d$-action by graph automorphisms with finite quotient) the Mahler measure of its Laplacian determinant polynomial is the growth rate of the complexity of finite quotients of G. Lehmer’s question, an open question about the roots of monic integral polynomials, is equivalent to a question about the complexity growth of edge-weighted 1-periodic graphs. Connections with knot theory are discussed.