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
    is it that hard this question ?2011-05-31
  • 0
    a) There need not be a single longest directed path. How is $L$ defined in that case? b) The distinction between $x_i$ and $\operatorname{rank}(x_i)$ seems unnecessary -- can't we just say that the graph is on the set $\{1,\dotsc,n\}$ and you want the expected value of $x_i$? c) Are $m$ and $k$ related in any way? It seems it would make more sense if they were the same? d) $m$ and/or $k$ themselves are random, and for any given $i$ there isn't an $x_i$ in some graphs. How to deal with that?2012-12-02
  • 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