Hostname: page-component-74656f9884-c52kr Total loading time: 0 Render date: 2026-11-08T23:06:21.485Z Has data issue: false hasContentIssue false
  • English
  • Français

Asymptotic Enumeration of Spanning Trees

Published online by Cambridge University Press:  21 July 2005

RUSSELL LYONS
RUSSELL LYONS
Affiliation:
Department of Mathematics, Indiana University, Bloomington, IN 47405-5701, USA (e-mail: rdlyons@indiana.edu, http://mypage.iu.edu/~rdlyons)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We give new formulas for the asymptotics of the number of spanning trees of a large graph. A special case answers a question of McKay [Europ. J. Combin. 4 149–160] for regular graphs. The general answer involves a quantity for infinite graphs that we call ‘tree entropy’, which we show is a logarithm of a normalized determinant of the graph Laplacian for infinite graphs. Tree entropy is also expressed using random walks. We relate tree entropy to the metric entropy of the uniform spanning forest process on quasi-transitive amenable graphs, extending a result of Burton and Pemantle [Ann. Probab. 21 1329–1371].

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 14 , Issue 4 , July 2005 , pp. 491 - 522
Copyright
© 2005 Cambridge University Press