Hostname: page-component-cd9895bd7-jkksz Total loading time: 0 Render date: 2024-12-23T09:43:34.863Z 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: [email protected], http://mypage.iu.edu/~rdlyons)
Get access Rights & Permissions [Opens in a new window]

Abstract

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].

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

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)