---
author:
- Russell Lyons
title: Asymptotic Enumeration of Spanning Trees
---

math.macros Ref.macros

.key

\#1[(\#1)\_]{} \#1[(\#1)\_]{} \#1[(\#1)\_]{} \#1[(\#1)\_]{} \#1[(\#1)\_]{} \#1[(\#1)]{} \#1[(\#1)]{} \#1,[\#1,]{} \#1,[\#1,]{} \#1,[\#1, ]{}

Methods of enumeration of spanning trees in a finite graph $\gh$ and relations to various areas of mathematics and physics have been investigated for more than 150 years. The number of spanning trees is often called the [**complexity**]{} of the graph, denoted here by $\cp(\gh)$. The best known formula for the complexity, proved in every basic text on graph theory, is called “the Matrix-Tree Theorem", which expresses it as a determinant. One is often interested in asymptotics of the complexity of a sequence of finite graphs that approach (in some sense) some infinite graph. Use of the Matrix-Tree Theorem typically involves calculating eigenvalues and their asymptotics. This often leads to a formula of the form $$\lim_{n \to\infty} {1 \over |\verts(\gh_n)|}  \log \cp(\gh_n) 
=
\int \log f$$ for some function $f$ on the unit cube of some Euclidean space, where $\verts(\gh_n)$ is the vertex set of $\gh_n$. One of the cases that is most well known, due to its connection with domino tilings, is that where the graphs $\gh_n$ approach the usual square lattice, i.e., 