3
$\begingroup$

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

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

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I certainly meant the sequence A001035, i.e. the first one. $\endgroup$ Oct 13, 2015 at 12:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .