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

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

2007-11-12

arxiv.org/abs/0711.1893v2

Combin. Probab. Comput. 17 (2008), 711-726.

Mathematics

Probability

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

Growth of the Number of Spanning Trees of the Erdös-Rényi Giant Component does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Growth of the Number of Spanning Trees of the Erdös-Rényi Giant Component, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Growth of the Number of Spanning Trees of the Erdös-Rényi Giant Component will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-269993