3
$\begingroup$

We are given a partially ordered set $P$. Let $L$ denote the set of all linear extensions of $P$ (or equivalently, the set of all topological sortings of the nodes).

We want to count the number of labeled DAGs which give rise to any of those linear extensions $L$.

For example, we are given a set of nodes $\{A,B,C\}$ and that $A < B$. The set of linear extensions $L$ is $\{ABC, ACB, CAB \}$. The number of DAGs with 3 nodes is 25, out of which 9 have a path from $A$ to $B$.

Has this problem been studied before? I was not able to find anything about it.

A related problem is that of counting the number of linear extensions of a given partially ordered set. This problem is #P-complete. Intuitively, my problem seems to be as hard as the one of counting linear extensions.

Edit: I probably gave a wrong formulation of my problem. I reformulated it to better match what I had in mind. I hope I got it right now.

  • 0
    I assume your underlying set is labeled, so you are counting DAGs on an explicit set, not isomorphism classes of DAGs?2012-11-21
  • 0
    @Marc Yes, labeled DAGs.2012-11-21
  • 0
    I edited the problem to match what I had in mind. I probably didn't formulate my problem correctly. I thank everybody that tried to answer.2012-11-21
  • 2
    In the second paragraph, you ask about DAGs that give rise to any of the linear extensions. In the third paragraph, you count the DAGs that have a path from $A$ to $B$; but these are the graphs whose transitive closure contains $P$, not the ones that give rise to an element of $L$. For instance, the DAG with a single edge from $A$ to $B$ doesn't give rise to a linear order. So I think you need to clarify which of these two counts you want.2012-11-28

3 Answers 3