×

zbMATH — the first resource for mathematics

Asymptotic enumeration of spanning trees. (English) Zbl 1076.05007
“Methods of enumeration of spanning trees in a finite graph \(G\) and relations to various areas of mathematics and physics have been investigated for more than 150 years.” The famous matrix-tree theorem (due originally to Kirchhoff) states that the number \(\tau(G)\) of spanning trees of a finite graph \(G\) is equal to any cofactor of the graph Laplacian matrix (the degree matrix of \(G\) minus the adjacency matrix of \(G\)). Use of this theorem often leads to an asymptotic approximation of the form \[ \frac{\log\tau(G_n)}{ | \text{vertex\;set\;of\;} G_n| } \to C, \] for some constant \(C\) expressible as an integral, as the cardinality of the vertex set goes to infinity. This paper gives an effective expression for \(C\) for “finite connected graphs with bounded average degree whose random weak limit is a probability measure on infinite rooted graphs” (covering many known cases). The expression is essentially in terms of the so-called “tree entropy”, the logarithm of a normalized determinant of the graph Laplacian for infinite graphs, and has an additional numeric value. Different interpretations of the tree entropy are also given.

MSC:
05A16 Asymptotic enumeration
05C30 Enumeration in graph theory
05C05 Trees
60C05 Combinatorial probability
PDF BibTeX XML Cite
Full Text: DOI arXiv