4
$\begingroup$

I am facing this problem for a long time, I wish I can find some help in here.

Let's consider a graph $G(V,E)$ such that an edge between a pair of node $u$ and $v$ exist with probability $p \in O(1)$. Let's assign identifiers for the vertices from 1 to $n$, where $n = |V|$. Now, direct each edge $(u,v)$ towards $v$ if $u > v$. We have what we call a random graph order P, which can be seen as a DAG (directed acyclic graph).

We define $L = (x_1, x_2, \ldots, x_m)$ as the longest directed path in DAG (or chain in P) in P. That is, $x_i > x_{i+1}$ for all $1 \leq i < m$. It is known that $|L| = \Theta(n)$. Define $\textit{rank}(x_i)$ as the position of $x_i$ in the set {1, ..., n} (that is, the first, the second, ..., the n-th element in the total order constructed from the identifiers of V).

Question. If we take any $x_i$ in L, what is expected rank of $x_i$?

My solution was to assume that $|L| = \frac{n}{t}$, and to assume that the path $L$ partitions the graph $G$ into $|L|$ layers. Thus, for the path $L = (x_1, \ldots, x_m)$ the expected rank of $x_i = (n - (t * i)) + \frac{1}{2} * t$. What do you think?

  • 0
    @joriki a) $L$ is any longest directed path. -- b) Yes,$i$guess this does not make any difference. -- c) $k$ is a typo - it supposed to be $m$ (yes, they are the same I changed it). -- note that $m = |L| \in \Theta(n)$2012-12-02

0 Answers 0