Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question

2 Answers 2

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.

share|improve this answer
    
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. –  Ori Gurel-Gurevich Mar 15 '12 at 17:30

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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