Hostname: page-component-745bb68f8f-hvd4g Total loading time: 0 Render date: 2025-02-06T14:13:31.494Z Has data issue: false hasContentIssue false
  • English
  • Français

Comparing Graphs of Different Sizes

Part of: Combinatorial probability Graph theory

Published online by Cambridge University Press:  02 May 2017

RUSSELL LYONS
RUSSELL LYONS*
Affiliation:
Department of Mathematics, Indiana University, 831 East 3rd Street, Bloomington, IN 47405-7106, USA (e-mail: rdlyons@indiana.edu)
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.

We consider two notions describing how one finite graph may be larger than another. Using them, we prove several theorems for such pairs that compare the number of spanning trees, the return probabilities of random walks, and the number of independent sets, among other combinatorial quantities. Our methods involve inequalities for determinants, for traces of functions of operators, and for entropy.

MSC classification

Primary: 05C05: Trees 60C05: Combinatorial probability
Secondary: 05C80: Random graphs 05C81: Random walks on graphs
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 26 , Issue 5 , September 2017 , pp. 681 - 696
Copyright
Copyright © Cambridge University Press 2017 

References

[1] Aldous, D. J. and Lyons, R. (2007) Processes on unimodular random networks. Electron. J. Probab. 12 #54 1454–1508.Google Scholar
[2] Antezana, J., Massey, P. and Stojanoff, D. (2007) Jensen's inequality for spectral order and submajorization. J. Math. Anal. Appl. 331 297–307.Google Scholar
[3] Benjamini, I., Lyons, R. and Schramm, O. (2015) Unimodular random trees. Ergodic Theory Dynam. Systems 35 359–373.Google Scholar
[4] Bhatia, R. (1997) Matrix Analysis , Vol. 169 of Graduate Texts in Mathematics, Springer.Google Scholar
[5] Chung, F. R. K., Graham, R. L., Frankl, P. and Shearer, J. B. (1986) Some intersection theorems for ordered sets and graphs. J. Combin. Theory Ser. A 43 23–37.Google Scholar
[6] Fontes, L. R. G. and Mathieu, P. (2006) On symmetric random walks with random conductances on ℤ d . Probab. Theory Rel. Fields 134 565–602.Google Scholar
[7] Heicklen, D. and Hoffman, C. (2005) Return probabilities of a simple random walk on percolation clusters. Electron. J. Probab. 10 #8 250–302.Google Scholar
[8] Janson, S. (2006) Conditioned Galton–Watson trees do not grow. In Fourth Colloquium on Mathematics and Computer Science: Algorithms, Trees, Combinatorics and Probabilities, DMTCS Proc. AG, pp. 331–334.CrossRefGoogle Scholar
[9] Löwner, K. (1934) Über monotone Matrixfunktionen. Math. Z. 38 177–216.Google Scholar
[10] Luczak, M. and Winkler, P. (2004) Building uniformly random subtrees. Random Struct. Alg. 24 420–443.Google Scholar
[11] Lyons, R. (2005) Asymptotic enumeration of spanning trees. Combin. Probab. Comput. 14 491–522.Google Scholar
[12] Lyons, R. (2010) Identities and inequalities for tree entropy. Combin. Probab. Comput. 19 303–313.Google Scholar
[13] 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.Google Scholar
[14] von Neumann, J. (1955) Mathematical Foundations of Quantum Mechanics (translated by Beyer, Robert T.), Princeton University Press.Google Scholar