Professor Russell Lyons


Indiana University


Tuesday, May 22, 2007 - 11:00am


MSTB 254

Methods of enumeration of spanning trees in a finite graph and relations to
various areas of mathematics and physics have been investigated for more
than 150 years. We will review the history and applications. Then we will
give new formulas for the asymptotics of the number of spanning trees of a
graph. A special case answers a question of McKay (1983) 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
[Fuglede-Kadison] determinant of the graph Laplacian for infinite graphs.
Proofs involve new traces and the theory of random walks.