# What is the expected length of the diameter of a special random graph?

Let $G=(n,p)$ be a random graph. For example, consider that $G$ is the following graph.

Initially, the edges of $G$ is undirected. A random $id\in R$ is assigned to each vertex of $G$. The $id$ of vertex $v$ is denoted by $id_{v}$. For each edge $e=(v,u)$, if $id_{v}>id_{u}$, $e$ is converted to a directed edge from $u$ to $v$, and if $id_{v}<id_{u}$, $e$ is converted to a directed edge from $v$ to $u$. A root is a vertex which all incident edges are outgoing edges. In the example, $V_{1}$ is a root.

Let $r$ be a root and $v$ be a none-root vertex which has the longest directed distance ($d_{r,v}$) from $r$. What is the expected value of $d_{r,v}$?

In the example, $d_{V_{1},V_{2}} = 1, d_{V_{1},V_{3}} = 1,d_{V_{1},V_{4}} = 1,d_{V_{1},V_{5}} = 2$, so $V_{5}$ is a non-root vetex which has the longest directed distance from the root.

## The following solution is my solution. But I can't compute some parts of it. Is there another solution?

There are $P(n,d_{r,v}-1)$ potential different paths with length $d_{r,v}$ from $r$ to $v$. The paths are labeled with numbers $1,...,P(n,d_{r,v}-1)$. The vertices of $i$th path are donoted by $r=\sigma^{i}_{1},\sigma^{i}_{2},...,\sigma^{i}_{d_{r,v}},\sigma^{i}_{d_{r,v}+1}=v$. $X_{i}\text{ }(1\leq i\leq P(n,d_{r,v}-1))$ is a random variable such that \begin{align} X_{i}=\begin{cases} 1 \quad\text{$i$th potential path, $\sigma^{i}$, is a valid path from $r$ to $v$.}\\ 0 \quad\text{o.w.} \end{cases} \end{align}
Thus, $E[d_{r,v}]$ is as follows $$E[d_{r,v}] = \sum_{i=1}^{P(n,d_{r,v}-1)}E[X_{i}]$$ What remains is computing $\Pr(X_{i}=1)$. $X_{i}=1$ when

1. There is a path from $r$ to $v$. The probability of it is $p^{d_{r,v}}$.
2. The $id$s of the path's vertices are monotonically increasing. The probability of it is $\frac{1}{(d_{r,v}+1)!}$.
3. There is no edge from $\sigma^{i}_{j}$ to $\sigma^{i}_{j+2}$ ($1\leq j\leq d_{r,v}-1$), for if there is an edge $(\sigma^{i}_{j},\sigma^{i}_{j+2})$, then the length of the longest directed path from $r$ to $v$ is not $d_{r,v}$ and is $d_{r,v}-1$. The probability of it is $(1-p)^{\frac{(d_{r,v}-1)(d_{r,v}-2)}{2}}$.
4. There is no path with length one from $\sigma^{i}_{j}$ to $\sigma^{i}_{j+3}$ ($1\leq j\leq d_{r,v}-2$). I can't compute it's probability!
5. There is no path with length two from $\sigma^{i}_{j}$ to $\sigma^{i}_{j+4}$ ($1\leq j\leq d_{r,v}-3$). I can't compute it's probability!

6. ...

• What range of values of $p$ are you interested in. Constant? Some specific function of $n$? Feb 12, 2018 at 20:37
• @MishaLavrov $C$ is a constant. $C < np < n^{\epsilon}$ Feb 13, 2018 at 4:58