# Combinatorial problem: Directed Acyclic Graph

How many unique landscapes exist in 5D DAG (directed acyclic graph)? There are $2^5$ points (eg: 00000, 00001, ... 11111) and $(2^5)!$ combinations.

The problem is a combinatorial problem. It should be fun and interesting, and I am interested in discussing the solution here as well.

It is classifying all distinct 5 dimensional landscapes. A landscape in 5-space is an assignment of edge direction to each edge between vertices such that a directed acyclic graph is formed (DAG).

Classification might include the number of peaks, basins, or a metric like that.

There are $(2^5)!$ combinations so obviously iterating through each combination and testing if it is a new landscape or an orientation of an old one won't work.

For example in the 2D case, there are $(2^2)!$ permutations = $24$. This 24 is made up of 3 landscapes. There are 8 orientations of each one.

I am reluctant to draw a picture at first, because maybe the way you visualize it will help you find a solution.

• Are you seeking the number of acyclic orientations of the 5D hypercube? This is given by the Tutte polynomial evaluated at $(2,0)$. It might be hard to compute the Tutte polynomial of this graph though. – Rebecca J. Stones Feb 7 '14 at 5:46
• Maybe. I am looking for unique orientations (ie: relabel the graph, is the structure the same as an already found structure?) – SwimBikeRun Feb 7 '14 at 7:51

This is really only a partial answer. What I think you are asking for is a calculation of the number of non-isomorphic acyclic orientations of the hypercube $Q_5$ where two orientations are isomorphic if there is an automorphism of $Q_5$ taking one to the other.

This can be done as an (almost) straightforward application of Burnside's Lemma as described by Peter Cameron in these notes.

First, as Rebecca suggested, you should recall the pretty amazing result of Stanley that if $\chi_G(x)$ denotes the chromatic polynomial of a graph $G$ on $n$ vertices, then $(-1)^n\chi_G(-1)$ is equal to the number of acyclic orientations of $G$.

Now, let $G$ be a graph and let $Aut(G)$ be its automorphism group. If $\sigma\in Aut(G)$, let $G/\sigma$ be the graph obtained by identifying the vertices in the orbits (i.e., cycles) of $\sigma$. This graph may contains loops and multiedges but for the statements below, multiedges may safely be replaced by a single edge.

Theorem: The number of non-isomorphic acyclic orientations that can be placed on $G$ is equal to $$\frac{1}{|Aut(G)|} \sum_{\sigma\in Aut(G)} (-1)^{sgn(\sigma)}\chi_{G/\sigma}(-1).$$

Note that if $G/\sigma$ has a loop, then $\chi_{G/\sigma}(x)=0$.

As for the hypercube graph $Q_n$, $Aut(Q_n)$ is isomorphic to the hyperoctohedral group, so in principle the above formula can be evaluated by anyone determined enough to do so. But even for $n=5$, Maple has trouble finding the chromatic polynomial of $Q_5$ using the basic command, and I'm not expert enough to coax an answer from it. Perhaps someone else can make that calculation.

On the other hand, the case $n=2$ is easy enough that I will do it here to illustrate the theorem. In this case, if we label the vertices of $Q_2$ in cyclic order as $1,2,3,4$, then $$Aut(Q_2)=\{(1),(1\,2\,3\,4), (1\,3)(2\, 4), (1\,4\,3\,2),(2\,4),(1\,2)(3\,4),(1\,3),(1\,4)(2\,3)\}.$$

But we really only need consider $\sigma\in\{(1),(1\,3)(2\, 4), (2\,4),(1\,3)\}$ since the other $\sigma$ are such that $G/\sigma$ has loops.

For $\sigma=(1)$, $G/\sigma=G$. The chromatic polynomial of the $4$-cycle is $(x-1)^4+(x-1)$.

For $\sigma=(1\,3)(2\,4)$, $G/\sigma$ is isomorphic to a path on $2$ vertices and so $$\chi_{G/\sigma}(x)=x(x-1).$$

For $\sigma=(1\,3)$ or $(2\,4)$, $G/\sigma$ is isomorphic to a path on $3$ vertices and so $$\chi_{G/\sigma}(x)=x(x-1)^2.$$

Applying the theorem gives that the number of non-isomorphic acycle orientations of $Q_2$ is obtained by plugging in $x=-1$ into $$\frac{1}{8}\left( (x-1)^4+(x-1) + x(x-1)- x(x-1)^2 - x(x-1)^2\right),$$ which, as you already know, is equal to $3$.

Added: A lower bound for $Q_5$ can be obtained using results found in a paper of Kahale and Schulman. Their Theorem 6 shows that $$(-1)^n\chi_G(-1)\geq \prod_{v\in V(G)} (deg(v)+1)!^{\frac{1}{\deg(v)+1}}.$$

Since $Q_5$ has 32 vertices, is $5$-regular and $|Aut(Q_5)|= 5!(2^5)$, we see that there are at least $$\left\lceil\frac{6!^{\frac{32}{6}}}{5!(2^5)}\right\rceil = 451, 622, 346, 888$$ non-isomorphic acyclic orientations. I have no idea how close that is to the exact number, but do you really need many more?

• Wow great answer! I have been working through it. I really appreciate it. I have a question I have been wondering about: How does the edge coloring or vertex theorems relate to my edge direction problem? Do I have one color for every vertice? If I color them by # of incoming and # of outgoing edges, I run into conflicts where two colors are next to each other. I could color the edge by whether it is incoming or outgoing, but how do I decide that? I suppose I could do it by the # of bits since one vertice's name will always have a higher number of bits associated with it – SwimBikeRun Feb 19 '14 at 5:41
• Ah I see the edge coloring's next description is no two vertices have an edge of the same color. So the method I proposed won't work. Any idea how to apply either the vertex or edge coloring? – SwimBikeRun Feb 19 '14 at 5:53
• It's a bit early where I am but I'm not sure what you're asking? Are you looking for a method to go for a vertex or edge coloring to a directed acyclic orientation? – Casteels Feb 19 '14 at 6:13
• Yes! I think so – SwimBikeRun Feb 19 '14 at 6:14
• @seteropere no that can't be correct since it evaluates to zero when $x=2$, but should evaluate to a positive number since $Q_5$ is bipartite. – Casteels Feb 28 '15 at 6:44