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