2
$\begingroup$

Given a set $V$, the number of DAGs with vertex set $V$ is super exponential in $|V|$. Are there known bounds on the number of DAGs over $V$? I am interested in "tight" lower bounds, if exist.

$\endgroup$
1
  • 1
    $\begingroup$ This answer is relevant: it gives a recursion for the number of DAGs on n vertices. It doesn't quite answer your question though, because it may be non-trivial to turn that into an explicit estimate. math.stackexchange.com/questions/554904/… $\endgroup$ – amomin Oct 23 '16 at 15:09
2
$\begingroup$

Here's a bound, although it's not a tight bound. The number of DAGs is lower-bounded by the number of undirected graphs, because every DAG may be converted to an UG by removing the orientations of the edges.

How many undirected graphs are there? For each pair of nodes, they may be either connected or disconnected (two options). If $|V| = p$, there are ${p \choose 2} = \frac{p(p - 1)}{2}$ distinct pairs of nodes. Therefore, the number of DAGs is lower-bounded by $2^{p(p-1 )/2}$.

We can upper-bound the number of DAGs with a similar argument. Ignoring the acyclicity requirement, every pair of nodes $A$ and $B$ may either be disconnected, connected $A \to B$, or connected $B \to A$ (three options). Thus the number of DAGs is upper-bounded by $3^{p(p-1 )/2}$.

$\endgroup$
1
  • $\begingroup$ Right, I should have showed that there's a one-to-many relationship between UGs and DAGs. By the way, "Every DAG may be converted to an UG" does not imply that "number of DAGs ≤ number of UGs", because two distinct DAGs may have the same adjacencies, so they would become identical UGs when the orientations are removed. $\endgroup$ – Lizzie Silver Mar 21 '18 at 4:56

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.