Suppose $G\sim G(n,p)$ with $p=\alpha\ln{n}/n$ for some large constant $\alpha$. I wish to show a certain "drift" property of $G$, which can roughly be phrased as follows: if $u$ is "not that far" from $v$, then "almost all" neighbours of $u$ are at least as far from $v$ as $u$ itself.
A few clarifications:
- "not that far" means at most $\frac{1}{2}$ the diameter of $G$, or perhaps a smaller fraction
- "almost all" means "all but a constant number of", perhaps all but 10, say
and a few related facts:
- It is known that the diameter is close to $\frac{\ln{n}}{\ln{\ln{n}}}$.
- Chung and Lu give in their paper "The Diameter of Sparse Random Graphs" estimates on the sizes of sets of vertices of a given distance from some root. For example, they show that if $\alpha\ge 1$, then \begin{equation*} \mathbb{P}\left(\exists v:\ |\Gamma_i(v)| > 9 (\alpha\ln{n})^i\right) = o(1) \end{equation*} (where $\Gamma_i(v)$ is the set of vertices of distance exactly $i$ from $v$). That makes sense, as all degrees of vertices in $G$ are roughly $\alpha\ln{n}$.
However, if $u$ is "not that far" from $v$, when estimating the number of its neighbours in $\Gamma_i(v)$ (for $i=d_G(u,v)-1$) one must condition on the fact that $u$ has at least one neighbour there, and that complicates things a little bit.
Do you have any idea of a simpler method to prove this, or perhaps a helpful reference?