Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I've been trying for a few days to figure out a proof of part $(iii)$ of Lemma 2.1 of this paper, on page 4, and I could definitely use some help. You don't need to understand any of the rest of the paper to understand what lemma 2.1 is saying, it's purely about a few properties of random graphs.

Could anyone explain how such a proof (just of part $(iii)$) might go? As far as I know, the "first moment method" is simply the observation that $\mathbb{P}(X>0) \leq \mathbb{E}(X)$.

We can condition this on "vertices $v$, $w$ are at distances at most $i$ from each other" but I can't really get anywhere with it. I guess the expected number of length-$i$ paths between 2 fixed vertices is $(n-2)(n-3)\ldots(n-i)p^i \sim d^i/n = n^{i\alpha - 1}$.

Conditioning on $d(v,w)\leq i$ (which is obviously not the same as necessarily having a path of length $i$ between the 2 vertices, although I think the probabilities of these events become arbitrarily close), I'm not sure how we pull out a $2/(1-i\alpha)$ out of the details. I think we can use part $(i)$ of the lemma to get out probabilities that a vertex is at distance at most $i$ from another, and probabilities that a vertex is at distance exactly $i$ from another (both approximately $d^i/n$).

After that I tried extending the first moment method to the statement $\mathbb{P}(X>\frac{2}{1-i\alpha}) \leq \frac{1-i\alpha}{2} \mathbb{E}(X)$ but again, I'm unclear where to go from here. I'd be really appreciative of a proof of this part of the lemma - it looks to be fairly simple, so I'm not sure what I'm missing.

Alternatively, if anyone has a reference which happens to prove this result then I would be more than happy to locate that, but I've looked through numerous books on random graphs and spent a lot of time searching online to no avail. Thank you for your help - Sam

share|improve this question
    
Bollobás' Random Graphs has a section on paths and cycles in random graphs (Chapter 8 I believe), though I'm afraid I can't remember anything on counting edges between vertices. –  Jak Apr 30 '12 at 3:48
    
Yes, I had a look through that already but no luck unfortunately, I've been stuck on this for days now. –  Samantha Terries Apr 30 '12 at 5:32
add comment

1 Answer

up vote 1 down vote accepted

I don't think any conditioning is required; as you suspected, this is a bit simpler than that. The formulation is slightly misleading because "If $w\in N_i(v)$" sounds like conditioning, but since $v$ and $w$ are joined by $0$ paths of length $i$ if $w\notin N_i(v)$, it's actually just saying that there are always fewer than $2/(1-i\alpha)$ paths of length $i$, so we just have to estimate the expected number $m(i,k)$ of pairs $v,w$ in $G(n,p)$ connected by $k$ paths of length $i$.

You've already calculated this expectation value for one such path between two fixed vertices. Neglecting overlapping paths at first, we can roughly estimate $m(i,k)$ by just taking the $k$-th power of your probability:

$$m(i,k)\approx\frac{n(n+1)}2\left(n^{i\alpha-1}\right)^k\sim\frac12 n^{(i\alpha-1)k-2}\;.$$

For $k\lt2/(1-i\alpha)$, this tends to zero, and thus so must the probability of there being any pair of vertices with $k$ disjoint paths of length $i$ between them.

Now one might think that overlaps would change this significantly, since a second path could reuse a lot of the edges of the first one and would thus produce fewer factors of $p$. However, this is not the case, since $np\sim n^\alpha$ with $\alpha\gt0$ and each additional factor of $p$ comes with an additional factor of $n$. Thus, we actually get a lower power of $n$ in total if we try to reuse edges. For instance, reusing the entire first path except for two new edges with one new vertex in between leads to a factor $np^2\sim n^{2\alpha-1}$, whereas a whole new path leads to a factor $n^{i\alpha-1}\ge n^{2\alpha-1}$. There are some combinatorial factors for the paths with reused edges, but these depend only on $i$ and $k$, not on $n$ and thus don't matter asymptotically; whether the expected value goes to zero depends only on the exponent of the leading term that corresponds to $k$ disjoint paths.

I believe it should be "at most $2/(1-i\alpha)$ paths of length $i$" instead of "fewer than", since the exponent is $0$ in case of equality and thus the result would be determined by the $n^{o(1)}$ factor in $d$. This can't be an error due to subtleties in the correlation argument above, since it already occurs for $i=2$ and there are only disjoint paths in that case anyway. In this case, for $\alpha=1/4$ we have $2/(1-i\alpha)=4$, so for $i=2$, $\alpha=1/4$, $k=4$ the exponent is $0$ and the expected number of pairs connected by $4$ paths of length $2$ can diverge or vanish depending on the $n^{o(1)}$ factor in $d$.

For the second part of (iii), the number of paths of length $i+1$ from $v$ to $w$ is bounded by the number $N_i(v)$ of vertices at a distance $i$ from $v$ times the maximal number of paths of length $i$ from $v$ to each of these vertices times the maximal proportion of edges between these vertices and $w$. The latter is a.a.s. less than $p+\delta$ for any $\delta\gt0$, and the other two factors are bounded by (i) and the first part of (iii). With $i=l-1$, altogether this yields the asymptotic upper bound

$$(1+\epsilon)d^i\frac2{1-i\alpha}p=\frac{2(1+\epsilon)}{1-(l-1)\alpha}\frac{d^l}n\lt\frac3{1-(l-1)\alpha}\frac{d^l}n\;.$$

share|improve this answer
add comment

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.