# Expected number of vertices a distance $k$ away in a random graph?

Given a random (undirected and unweighted) graph $G$ on $n$ vertices where each of the edges has equal and independent probability $p$ of existing (see Erdős–Rényi model). Fix some vertex $u\in G$. I want to know what is the expected number of vertices a distance $k$ away (where distance means the shortest distance). I can only figure out that we expect there to be $(n-1)p$ vertices a distance 1 away since each of the possible $(n-1)$ edges outgoing from $u$ have probability $p$ of existing, but I am having trouble generalizing from this local property. Maybe someone can handle the task or perhaps point me in the right direction via a paper?

If it makes it easier, assume that $G$ is connected (as it almost surely is as $n\rightarrow \infty$, which is the case I am interested about). As a subproblem of almost equal importance, I would in particular like to know what is the expected longest shortest distance from vertex $u$ and how many vertices are away from vertex $u$ at that distance (subproblem with the maximum possible $k$).

Note: (1) The graph does not have a bound on the degree of the vertex (there could be as many as $n-1$ adjacent vertices to $u$).

• This problem has a lot of symmetry. I like to think of it as the complete graph with weights $p$ on the edges. I think the assumption that $G$ is connected is probabilistically speaking unnatural. – Patrick Da Silva Jan 5 '14 at 5:12
• There are some easy $k$'s where you can compute explicitly ; for $k = n-1$, the only way that a vertex is at a distance $n-1$ is if you have a path graph ; for there must be a path of length $n-1$ from $u$ to some vertex $v$, hence you have a sequence $$u= u_0, e_1 = \{u_0,u_1\}, e_2 = \{u_1,u_2\}, \cdots , e_{n-1} = \{ u_{n-1},u_n\}, \quad u_n = v.$$ Any edge outside the set $\{e_1,\cdots,e_{n-1}\}$ induces a path of length shorter than $n-1$ between $u$ and $v$, so you get a path graph. Computing the expectation becomes combinatorics in this case. – Patrick Da Silva Jan 5 '14 at 5:16
• There are $\binom n2$ possible edges and $n-1$ of them must be in the graph, so the probability that a particular path happens is $p^{n-1} (1-p)^{\binom n2 - (n-1)}$ ; the number of possible paths is simply $n!$, i.e. the number of way to order $u_1,\cdots,u_n$. Your final answer is $$n! p^{n-1} (1-p)^{\binom n2 - (n-1)} = n! p^k (1-p)^{\binom n2 - k}.$$ – Patrick Da Silva Jan 5 '14 at 5:19
• @PatrickDaSilva, oh okay. I see what you were continuing your proof which you started in the comment prior. Good special case, which might help in the general case. Thanks. – bourbaki4481472 Jan 5 '14 at 5:27
• I don't think it would be too hard to obtain a formula for the expected number of vertices at distance at most $k$ (and then compute the $k$ case minus the $k-1$ case) by simply averaging the probability that a random path between $u$ and some vertex $v$ of length $k$ happens. Otherwise I don't see how this could be solved. – Patrick Da Silva Jan 5 '14 at 5:30

Let $\lambda=np$. Then the average distance $k$ between two randomly picked vertices from the giant component is $$k\sim \frac{\log n}{\log \lambda},$$ given that the giant component exists ($\lambda>1$). A proof can be found in, e.g., Durrett's Random graph dynamics.
This result implies that the actual number for your first question is $$\lambda^k.$$ However, this only works if $pn\to\lambda<\infty$ when $n\to\infty$. What about the case $p=const$? Here is an exercise: Show that the diameter of the E-R random graph in this case is 2 a.a.s.
• It's interesting that you get $\lambda^d$, because the cases $k=1$ and $k=n-1$ have a geometric random variable flavor. – Patrick Da Silva Jan 5 '14 at 5:55
• @PatrickDaSilva The results I state are asymptotic. (I changed my $d$ for $k$ as in the original question). I do not quite get what you calculate in the case "$k=n-1$". – Artem Jan 5 '14 at 6:04
• @ijkilchenko Ups, apologies. Asymptotically almost surely. Another terminology is w.h.p. (with high probability). Probability of something going to 1 when $n\to\infty$ – Artem Jan 5 '14 at 6:13