Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-24T22:36:07.746Z Has data issue: false hasContentIssue false
  • English
  • Français

Growth of the Number of Spanning Trees of the Erdős–Rényi Giant Component

Published online by Cambridge University Press:  01 September 2008

RUSSELL LYONS ,
RON PELED  and
ODED SCHRAMM
RUSSELL LYONS
Affiliation:
Department of Mathematics, Indiana University, Bloomington, IN 47405-5701, USA (e-mail: [email protected])
RON PELED
Affiliation:
Department of Statistics, University of California at Berkeley, 367 Evans Hall, Berkeley, CA 94720-3860, USA (e-mail: [email protected])
ODED SCHRAMM
Affiliation:
Microsoft Research, One Microsoft Way, Redmond, WA 98052, USA
Get access Rights & Permissions [Opens in a new window]

Abstract

The number of spanning trees in the giant component of the random graph (n, c/n) (c > 1) grows like exp{m(f(c)+o(1))} as n → ∞, where m is the number of vertices in the giant component. The function f is not known explicitly, but we show that it is strictly increasing and infinitely differentiable. Moreover, we give an explicit lower bound on f′(c). A key lemma is the following. Let PGW(λ) denote a Galton–Watson tree having Poisson offspring distribution with parameter λ. Suppose that λ*>λ>1. We show that PGW(λ*) conditioned to survive forever stochastically dominates PGW(λ) conditioned to survive forever.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 17 , Issue 5 , September 2008 , pp. 711 - 726
Copyright
Copyright © Cambridge University Press 2008

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. and Pitman, J. (1998) Tree-valued Markov chains derived from Galton–Watson processes. Ann. Inst. H. Poincaré Probab. Statist. 34 637–686.CrossRefGoogle Scholar
[2]Benjamini, I. and Schramm, O. (1996) Percolation beyond Z d, many questions and a few answers. Electron. Comm. Probab. 1 71–82 (electronic).CrossRefGoogle Scholar
[3]Bollobás, B. (2001) Random Graphs, Vol. 73 of Cambridge Studies in Advanced Mathematics, 2nd edn, Cambridge University Press.Google Scholar
[4]Erdős, P. and Rényi, A. (1960) On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutató Int. Közl. 5 17–61.Google Scholar
[5]van der Hofstad, R. and Járai, A. A. (2004) The incipient infinite cluster for high-dimensional unoriented percolation. J. Statist. Phys. 114 625–663.CrossRefGoogle Scholar
[6]Luczak, M. and Winkler, P. (2004) Building uniformly random subtrees. Random Struct. Alg. 24 420–443.CrossRefGoogle Scholar
[7]Lyons, R. (2005) Asymptotic enumeration of spanning trees. Combin. Probab. Comput. 14 491–522.CrossRefGoogle Scholar
[8]Lyons, R. (2007) Identities and inequalities for tree entropy. Preprint, arXiv:0712.3035.Google Scholar
[9]Piau, D. (1998) Théorème central limite fonctionnel pour une marche au hasard en environnement aléatoire. Ann. Probab. 26 1016–1040.CrossRefGoogle Scholar
[10]Pitman, J. (1998) Enumerations of trees and forests related to branching processes and random walks. In Microsurveys in Discrete Probability (D. Aldous and J. Propp, eds), Vol. 41 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., AMS, Providence, RI, pp. 163–180.CrossRefGoogle Scholar