First two definition:

(A) Random Directed Graph:

Suppose we have a random $DAG(n, p)$. Here is how it's generated:

  • Put n distinct nodes on a line, and connect each node in the $i$th order to any node after that; This would form a complete directed graph with $n$ nodes.

  • Sample each edge with probability $p$.

The resulting graph will be directed, and acyclic.

(B) Transitive Closure:

Transitive closure of a graph $\text{closure}(G)$ is the result of connecting all the node pairs $i-j$ (via a direct edge $i \rightarrow j$) such that there is a path connecting $i$ to $j$.

The question is:

what is the expected number of edges in $\text{closure}(DAG(n, p))$?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.