6
$\begingroup$

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

  • 0
    Yes, I had a look through that already but no luck unfortunately, I've been stuck on this for days now.2012-04-30

1 Answers 1

1

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\;.$