# number of edges in a transitive closure of a random directed graph

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))$?