Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-09T11:24:20.312Z Has data issue: false hasContentIssue false
  • English
  • Français

Identities and Inequalities for Tree Entropy

Published online by Cambridge University Press:  15 December 2009

RUSSELL LYONS
RUSSELL LYONS*
Affiliation:
Department of Mathematics, Indiana University, Bloomington, IN 47405-5701, USA (e-mail: rdlyons@indiana.eduhttp://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.

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.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 19 , Issue 2 , March 2010 , pp. 303 - 313
Copyright
Copyright © Cambridge University Press 2009

References

[1]Aldous, D. J. and Lyons, R. (2007) Processes on unimodular random networks. Electron. J. Probab. 12 #54, 1454–1508 (electronic).CrossRefGoogle Scholar
[2]Benjamini, I. and Schramm, O. (2001) Recurrence of distributional limits of finite planar graphs. Electron. J. Probab. 6 #23 (electronic).CrossRefGoogle Scholar
[3]Chung, F. R. K. and Yau, S. T. (1999) Coverings, heat kernels and spanning trees. Electron. J. Combin. 6 #12 (electronic).Google Scholar
[4]Dixmier, J. (1981) Von Neumann Algebras, Vol. 27 of North-Holland Mathematical Library, North-Holland, Amsterdam.Google Scholar
[5]Elek, G. and Szabó, E. (2005) Hyperlinearity, essentially free actions and L 2-invariants: The sofic property. Math. Ann. 332 421–441.CrossRefGoogle Scholar
[6]Fack, T. and Kosaki, H. (1986) Generalized s-numbers of τ-measurable operators. Pacific J. Math. 123 269–300.CrossRefGoogle Scholar
[7]Fuglede, B. and Kadison, R. V. (1952) Determinant theory in finite factors. Ann. of Math. (2) 55 520–530.CrossRefGoogle Scholar
[8]Haagerup, U. and Schultz, H. (2007) Brown measures of unbounded operators affiliated with a finite von Neumann algebra. Math. Scand. 100 209–263.CrossRefGoogle Scholar
[9]Kadison, R. V. and Ringrose, J. R. (1997) Fundamentals of the Theory of Operator Algebras I: Elementary Theory, Vol. 15 of Graduate Studies in Mathematics, AMS, Providence, RI.CrossRefGoogle Scholar
[10]Kadison, R. V. and Ringrose, J. R. (1997) Fundamentals of the Theory of Operator Algebras II: Advanced Theory, Vol. 16 of Graduate Studies in Mathematics, AMS, Providence, RI.CrossRefGoogle Scholar
[11]Lyons, R. (2005) Asymptotic enumeration of spanning trees. Combin. Probab. Comput. 14 491–522.CrossRefGoogle Scholar
[12]Lyons, R., Peled, R. and Schramm, O. (2008) Growth of the number of spanning trees of the Erdős–Rényi giant component. Combin. Probab. Comput. 17 711–726.CrossRefGoogle Scholar
[13]McKay, B. D. (1981) Spanning trees in random regular graphs. In Proc. Third Caribbean Conference on Combinatorics and Computing (C. C. Cadogan, ed.), pp. 139–143.Google Scholar
[14]McKay, B. D. (1983) Spanning trees in regular graphs. Europ. J. Combin. 4 149–160.CrossRefGoogle Scholar
[15]Murray, F. J. and von Neumann, J. (1936) On rings of operators. Ann. of Math. (2) 37 116–229.CrossRefGoogle Scholar