# What part of digraphs are posets?

Let $D_n$ denote the collection of all directed graphs on vertex set $[n]=\{1,\ldots, n\}$.

Let $P_n$ denote the subcollection of all digraphs in $D_n$, which have the structure of a partial order.

What is the proportion $\frac{\left| P_n\right|}{\left| D_n\right|}$?

• It's $1$? All sets can be partially ordered, so $P_n=D_n$. Oct 13, 2015 at 10:50
• Oh, now I understand. A graph here is a drawing, not a set. Oct 13, 2015 at 10:53

https://oeis.org/A001035 gives the number of posets on $n$ labelled nodes, while https://oeis.org/A003024 counts the number of directed acyclic graphs on $n$ labelled nodes; the distinction is, I think, that the graphs in the first sequence are explicitly transitively closed (if $a \to b$ and $b \to c$, then $a \to c$).
There are $3^\binom{n}{2}$ possible directed graphs on $n$ labelled nodes, since each edge can either not exist, or be in one of two directions. The sequences I cite above do not seem to have closed forms.
I had stated in an earlier comment that the only impediment to a digraph having a poset structure is the existence of a directed cycle, because that would violate transitivity. I think that actually it is ambiguous here whether you are taking $P_n$ to be the sequence $\mbox{A001035}$ or $\mbox{A003024}$; the digraphs in the latter sequence induce a poset structure by transitive closure, while the poset structure in the former sequence is explicit.