# lower bounds on the number of directed acyclic graphs with $n$ vertices

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.

• 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/… – amomin Oct 23 '16 at 15:09

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