Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-26T03:47:40.248Z 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: [email protected]://mypage.iu.edu/~rdlyons/)
Get access Rights & Permissions [Opens in a new window]

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.

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

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

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