3
$\begingroup$

I saw stated in a paper the following result but without a reference or a proof.

Let $G$ be an Erdos-Renyi random graph with $n$ nodes and probability of connection $c/n$ with $c>1$. Let $H$ be its giant component (which exists and has $\alpha(c)n$ nodes almost surely where $\alpha$ is a well known function). Then the graph $H$ has paths with only one connection to the rest of the graph of length $O(\log n)$ asymptotically almost surely.

Can somebody show me why is this true or give me a reference? Thanks a lot!

$\endgroup$

2 Answers 2

3
$\begingroup$

Start with some/random vertex $v_1$. With probability $a_1=n p (1-p)^{n-1}\approx ce^{-c}$ it has exactly one neighbor, $v_2$. The probability that $v_2$ has exactly one additional neighbor, $v_3$, is $a_2=n p (1-p)^{n-2}$ which is also close to $ce^{-c}$. The probability that each subsequent vertex has exactly one new neighbor is again roughly $A=c e^{-c}$. This means that with probability roughly $A^k$ we see a path of length $k$ beginning at $v_1$. If $k=c_1 \log n$ for some small enough $c_1$ then this probability is $n^{-c_2}$ for some $c_2<1$.

After these $k$ steps there is a fixed probability (roughly $\alpha(c)$) that the last vertex $v_k$ is then connected to the giant component. So this means that the expected number of paths of logarithmic length connected to the giant component is large ($n^{1-c_2}$). We then use standard arguments (say, second moment) to show that with high probability there are such paths.

$\endgroup$
1
  • $\begingroup$ ght: Expectation is linear regardless of dependencies. To get that there is such a path whp, you use second moment. That is, you estimate the variance. It is rather easy since these events for different starting vertices are asymptotically independent. $\endgroup$ Mar 15, 2012 at 17:30
1
$\begingroup$

in the reference corner, check out:

  • Rick Durrett's "Random Graph Dynamics" (2007), chapter 2, section 4
  • Bela Bollobas' "Random Graphs" (2000), chapter 7, section 1

hope this helps

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.