1
$\begingroup$

Given a topological sorting $>$ over a set of elements $N$, how many possible DAGs with vertex set $N$ that are consistent with $>$ ? ( note that a DAG may be consistent with other orders in addition to $>$ )

If it is not known, can we bound it by some number?

My attempt: Assume $x_1>x_2>\dots>x_n$ to be the given order. For the first element $x_1$, we can connect it to any (subset) of the rest. Thus, for the element at position $i\in [1,2,\dots,n]$ we can connect it to $\sum\limits_{k=0}^{n-i} \binom{n-i}{k}$ other elements and finally we have $\sum\limits_{i=1}^{n}\sum\limits_{k=0}^{n-i} \binom{n-i}{k}$ possible DAGs over $>$.

Does this give the correct number for it?

$\endgroup$
1
$\begingroup$

There are $\binom{n}2$ pairs of vertices. Any pair can be connected, and if it is connected, the direction is unique. Thus, there are $2^{\binom{n}2}$ possible DAGs consistent with a given linear order on $[n]$, one for each subset of the pairs of vertices.

Your calculation simplifies to

$$\sum_{i=1}^n\sum_{k=0}^{n-i}\binom{n-i}k=\sum_{i=1}^n2^{n-i}=\sum_{i=0}^{n-1}2^i=2^n-1\;,$$

which is clearly too small. The problem is that the outer summation should be a product: each combination of connections for one vertex can be combined with any combination of connections for a later vertex. Then you get the correct value:

$$\prod_{i=1}^n\sum_{k=0}^{n-i}\binom{n-i}k=\prod_{i=1}^n2^{n-i}=\prod_{i=0}^{n-1}2^i=2^{\sum_{i=0}^{n-1}i}=2^{\binom{n}2}\;.$$

$\endgroup$
2
  • $\begingroup$ What a bless this answer is. Direct, clear and to the point. You are truly a hero :) Thanks. Is there any reference/book where I can find this value so I can cite it? $\endgroup$ – seteropere Mar 15 '15 at 8:11
  • 1
    $\begingroup$ @seteropere: You’re very welcome. It wouldn’t surprise me at all if there were some reference that you could cite, but I don’t know one, I’m afraid. You can almost cite OEIS A006125, which notes that it’s the number of graphs on $n$ labelled nodes; you have directed graphs, but the direction of each edge is predetermined, so in effect you’re counting undirected graphs. $\endgroup$ – Brian M. Scott Mar 15 '15 at 8:15

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.