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

preprint2008arXivOpen access

Abstract

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

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.