Spanning Trees and Mahler Measure

Abstract

The complexity of a finite connected graph is its number of spanning trees; for a non-connected graph it is the product of complexities of its connected components. If $G$ is an infinite graph with cofinite free ${\mathbb{Z}}^d$-symmetry, then the logarithmic Mahler measure $m(\Delta )$ of its Laplacian polynomial $\Delta$ is the exponential growth rate of the complexity of finite quotients of $G$. It is bounded below by $m(\Delta ({\mathbb{G}}_d))$, where ${\mathbb{G}}_d$ is the grid graph of dimension $d$. The growth rates $m(\Delta ({\mathbb{G}}_d))$ are asymptotic to $\log 2d$ as $d$ tends to infinity. If $m(\Delta (G))\ne 0$, then $m(\Delta (G))\ge \log 2$. An application to determinant growth rates of families of alternating links arising from planar graphs is given.

12 pages, 1 figure

Cited by in corpus (3)

• On complexity of cyclic coverings of graphs
• Determinant density and biperiodic alternating links
• On rationality of generating function for the number of spanning trees in circulant graphs