| doi:10.1017/S0963548308009188 Printed in the United Kingdom Growth of the Number of Spanning Trees of the Erdős–Rényi Giant Component (2009) | |||||||||||||||
Abstract | |||||||||||||||
| The number of spanning trees in the giant component of the random graph G(n, c/n) (c>1) grows like exp{m(f(c)+o(1))} as n →∞,wherem 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. 1. | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||