Growth of the Number of Spanning Trees of the Erdös-Rényi Giant Component

Abstract

The number of spanning trees in the giant component of the random graph $\G(n, c/n)$ ($c>1$) grows like $\exp \left\{m\right(f(c)+o(1)\left)\right\}$ as $n\to \infty$, 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^{\prime }(c)$. A key lemma is the following. Let $\PGW(λ)$ denote a Galton-Watson tree having Poisson offspring distribution with parameter $\hat{I}»$. Suppose that $\hat{I}{»}^{\ast }>\hat{I}»>1$. We show that $\PGW(λ^*)$ conditioned to survive forever stochastically dominates $\PGW(λ)$ conditioned to survive forever.