Combinatorics, Probability and Computing

Paper

Identities and Inequalities for Tree Entropy

RUSSELL LYONSa1

a1 Department of Mathematics, Indiana University, Bloomington, IN 47405-5701, USA (e-mail: rdlyons@indiana.edu http://mypage.iu.edu/~rdlyons/)

Abstract

The notion of tree entropy was introduced by the author as a normalized limit of the number of spanning trees in finite graphs, but is defined on random infinite rooted graphs. We give some new expressions for tree entropy; one uses Fuglede–Kadison determinants, while another uses effective resistance. We use the latter to prove that tree entropy respects stochastic domination. We also prove that tree entropy is non-negative in the unweighted case, a special case of which establishes Lück's Determinant Conjecture for Cayley-graph Laplacians. We use techniques from the theory of operators affiliated to von Neumann algebras.

(Received December 28 2007)

(Revised August 09 2009)

(Online publication December 15 2009)

Footnotes

Research partially supported by Microsoft Research and NSF grants DMS-0406017 and DMS-0705518.