Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-18T17:51:12.131Z Has data issue: false hasContentIssue false

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
Affiliation:
Department of Mathematics, Indiana University, Bloomington, IN 47405-5701, USA (e-mail: rdlyons@indiana.edu)
RON PELED
Affiliation:
Department of Statistics, University of California at Berkeley, 367 Evans Hall, Berkeley, CA 94720-3860, USA (e-mail: peledron@stat.berkeley.edu)
ODED SCHRAMM
Affiliation:
Microsoft Research, One Microsoft Way, Redmond, WA 98052, USA
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 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.

Information

Type
Paper
Copyright
Copyright © Cambridge University Press 2008