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

<p>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 &gt; v$. We have what we call a <em>random graph order</em> $P$. </p>

<p>We define $L = (x_1, x_2, \ldots, x_m)$ as the longest directed path in $P$. That is, $x_i &gt; x_{i+1}$ for all $1 \leq i &lt; k$.  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$).</p>

<blockquote>
  <p><strong>Question.</strong> If we take any $x_i \in L$, what is expected rank of $x_i$?</p>
</blockquote>

<p>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?</p>

CC BY-SA 3.0
2011-05-30T09:13:01.190Z
Hi @Ahmed, I modified your question with LaTeX. But there are some notations that is unclear to me (e.g. t and ti in the last paragraph.) Would you mind to explain and edit your question to make it clearer?
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2011-05-30T14:23:56.260Z
Hi @Hsien, thank you for the edit ! :) I modified wat was requested
AJed
CC BY-SA 3.0
2011-05-31T21:05:49.017Z
is it that hard this question ?
AJed
CC BY-SA 3.0
2011-06-01T12:08:42.653Z
The statement that p = O(1) is meaningless since p cannot possibly be more than 1.  Do you mean that p = Theta(1), i.e., that it is a fixed constant that does not depend on n?
James King
<graph-theory><co.combinatorics>
The rank of nodes in the longest directed path of a random DAG
AJed
# The rank of nodes in the longest directed path of a random DAG

(Asked by: username_0 on 2011-05-30)

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$.

We define $L = (x\_1, x\_2, \ldots, x\_m)$ as the longest directed path in $P$. That is, $x\_i > x\_{i+1}$ for all $1 \leq i < k$. 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?

**Tags:** graph-theory, co.combinatorics
> **Comments:**
> **username_1**: Hi @Ahmed, I modified your question with LaTeX. But there are some notations that is unclear to me (e.g. t and ti in the last paragraph.) Would you mind to explain and edit your question to make it clearer?  
> **username_0**: Hi @Hsien, thank you for the edit ! :) I modified wat was requested  
> **username_0**: is it that hard this question ?  
> **username_2**: The statement that p = O(1) is meaningless since p cannot possibly be more than 1.  Do you mean that p = Theta(1), i.e., that it is a fixed constant that does not depend on n?  

---

## 0 answers

