1
$\begingroup$

I am looking at doing some basic validation on a database of st-dags. It would be useful to have:

  1. A formula for the number of non-isomorphic st-dags with n vertices

  2. A formula for the same with n vertices and p edges

Is there such a formula, and is there some literature (accessible to the non-mathematician) that might discuss any special properties of st-dags.

$\endgroup$

2 Answers 2

5
$\begingroup$

This is not a formula, but a method of counting the graphs in OP faster than straightforward enumeration. It's superpolynomial in complexity (although sub-exponential).

Let's start with a recurrence for the number $a_n$ of labelled directed acyclic graphs on $n$ vertices: $a_0 = 1$, and for any $n \geq 1$ $$a_n = \sum_{k = 1}^n (-1)^{k - 1} {n \choose k} a_{n - k} 2^{k(n - k)}.$$ This is inclusion-exclusion principle applied to the number $k$ of sources in the graph. If we want the graph to have a single sink, we simply forbid the empty graph, and each of the new sources to not have any outgoing edges, resulting in a recurrence $a'_{0} = 1$, $a'_{1} = 1$, and for any $n \geq 2$ $$a'_n = \sum_{k = 1}^n (-1)^{k - 1} {n \choose k} a'_{n - k} (2^{n - k} - 1)^k.$$ Finally, to also have a single source, for the final set of sources we tweak the inclusion-exclusion weights: having $k$ new sources on the final step has weight $(-1)^{k - 1} \cdot k$. One can see that only the graphs with a single source are not cancelled out (and are counted once), thus $$a''_n = \sum_{k = 1}^n (-1)^{k - 1} {n \choose k} k a'_{n - k} (2^{n - k} - 1)^k.$$

To count unlabelled graphs of this kind (we denote the numbers $b_n$, $b'_n$, $b''_n$ similar to the above), we combine the above approach with Burnside's lemma. Let $S_{n - 1}$ be the symmetric group acting on all $n$ vertices except for the unique sink. Then the number of unlabelled graphs is given by $b''_n = \frac{1}{(n - 1)!} \sum_{\pi \in S_{n - 1}} a''_{\pi}$, where $a''_{\pi}$ is the number of labelled single source, single sink DAGs stabilized by the permutation $\pi$. Clearly, $a''_{\pi}$ depends only on the conjugation class (cyclic structure) of $\pi$, so we can write $a''_{\lambda}$ for a partition $\lambda$ of $n-1$.

With a slightly more sophisticated version of inclusion-exclusion, we have $$a'_{\lambda} = \sum_{\varnothing \neq \mu \subset \lambda} (-1)^{|\mu|} {\lambda \choose \mu} a'_{\lambda - \mu} \prod_{i \in \mu} \left(2 \prod_{j \in \lambda - \mu} 2^{(i, j)} - 1\right).$$ The notation makes sense if $\lambda$ and $\mu$ are treated as multisets. Similarly, one can show that $$a''_{\lambda} = \sum_{\varnothing \neq \mu \subset \lambda} (-1)^{|\mu|} {\lambda \choose \mu} \omega(\mu) a'_{\lambda - \mu} \prod_{i \in \mu} \left(2 \prod_{j \in \lambda - \mu} 2^{(i, j)} - 1\right),$$ where $\omega(\mu)$ is the number of summands $1$.

The complexity of this solution is roughly $Poly(n) $A000712$(n) \sim Poly(n) exp(\frac{2\pi}{\sqrt{3}}\sqrt{n})$. This is an improvement of my initial approach from the comments to another answer, and, implemented in C++, produces answers up to $n = 40$ in about two minutes.

To count unlabelled graphs of this kind with prescribed number of edges, one can ostensibly modify this approach to operate with generating polynomials $\sum_{e = \text{# of edges}} c_e x^e$ instead of numbers for values of $a_n$, $a_{\lambda}$, $a'_{\lambda}$, etc.

$\endgroup$
5
  • $\begingroup$ I tried to implement your solution (a''), but it did not work. Already for n=2 I get 2 instead of 1. Can you maybe clarify/correct this? $\endgroup$ Commented Jul 22, 2021 at 22:53
  • $\begingroup$ @Simdi Do you refer to $a''_n$ or $a''_{\lambda}$? Please link your implementation so I can locate the problem. $\endgroup$ Commented Jul 26, 2021 at 11:59
  • $\begingroup$ I refer to the former. Here's my implementation. $\endgroup$ Commented Jul 26, 2021 at 19:03
  • 1
    $\begingroup$ @Simdi Ah but $a''_n$ count labelled graphs. There are indeed 2 graphs in question for $n=2$. In fact larger values produced by your code look correct to me as well. $\endgroup$ Commented Jul 28, 2021 at 18:52
  • $\begingroup$ Ah, yes you are absolutely right. Thanks! $\endgroup$ Commented Jul 28, 2021 at 20:21
1
$\begingroup$

I do not have a formula, but here is a sample SageMath code that generates all st-dags on $n$ vertices:

from sage.combinat.gray_codes import product as gc_product

def stDAGs(n):
    if n==1:
        yield DiGraph([[0],[]])
        return
    elif n==2:
        yield DiGraph([(0,1)])
        return

    for P in Posets(n-2):
        H = P.hasse_diagram()
        for t in P.maximal_elements():
            H.add_edge(t,n-2)
        for t in P.minimal_elements():
            H.add_edge(n-1,t)

        E = list( set(H.transitive_closure().edges(labels=False)) - set(H.edges(labels=False)) )

        G = H.copy()
        C = G.canonical_label()
        CC = set(C.dig6_string())
        yield C


        for e,d in gc_product([2]*len(E)):
            if d>0:
                G.add_edge(E[e])
            else:
                G.delete_edge(E[e])
            C = G.canonical_label()
            dig6 = C.dig6_string()
            if dig6 not in CC:
                CC.add(dig6)
                yield C

Then the number of such graphs with $n$ vertices can be obtained as

def f(n):
    return sum(1 for d in stDAGs(n))

which for $n=1,2,\dots,8$ gives

1, 1, 2, 10, 98, 1960, 80176, 6686760

These counts do not appear in the OEIS - so it's likely that little is known about them. I've added them as sequence A345258.

The above code can be easily adjusted to take into account the number of edges in each graph.

$\endgroup$
17
  • 1
    $\begingroup$ Next value 1129588960 . $\endgroup$ Commented Jun 12, 2021 at 3:11
  • 1
    $\begingroup$ @MaxAlekseyev I have a program for finding all the acyclic orientations of a graph. I fed all the connected graphs with 9 vertices into it and counted how many of the outputs had only one source and one sink. I forget exactly but I think it only took a minute or two. It could be done faster, but the next size up would be much harder. $\endgroup$ Commented Jun 13, 2021 at 14:15
  • 2
    $\begingroup$ I programmed the $n-2\to n$ method and it does $n=9$ in 3 seconds. The next one is 384610774696 in 10 minutes. I will edit OEIS when I do $n=11$ which will take 30 or 40 hours. The reason for the speed is that most of the acyclic orientations on $n-2$ vertices have trivial automorphism group, in which case the number of extensions can be calculated from the numbers of sources and sinks. $\endgroup$ Commented Jun 14, 2021 at 7:49
  • 1
    $\begingroup$ It's a fun combinatorial exercise to count these graphs efficiently. Here are my results up to $n = 25$: pastebin.com/Kn29mTFt $\endgroup$ Commented Jun 14, 2021 at 21:10
  • 2
    $\begingroup$ Up to $n = 30$ (took about 15 more minutes): pastebin.com/mkVNKChD $\endgroup$ Commented Jun 14, 2021 at 21:27

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.