Main Question: Assume an n-cube, which consists of $2^n$ vertices. Now there are $n!$ possible paths of length $n$ from vertex $0$ to vertex $2^n-1$. Assume each path has color blue when starting at $0$ but can change to red when crossing a vertex at distance $d$ (with $0<d<n$) at most once and then stays red. How many different colorings of the graph exist?

The paths are coupled which can be seen in this example: Assume a 4-cube, and vertices labeled by the binary representations of its corresponding integer. A path edges are being blue from $0000 \rightarrow 0100$ and $0100 \rightarrow 0110 $. It then changes at $v = 0110$ to red. Now every other path starting from $0000$ that crosses $v$ has to be red either before crossing $v$ or changing color at $v$. In this example the two paths ($0110 \rightarrow 1110 \rightarrow 1111$ and $0110 \rightarrow 0111 \rightarrow 1111$) of length $2$ from $v$ to $1111$ are both red. This example can be seen in this fig. 1.

Figure 1: Example of the dynamics and an allowed configuration.

On the other hand, the configuration in fig. 2 is not allowed. as the edge $0111 \rightarrow 1111$ is blue, but due to the color change in $0100$ this is prohibited. The path $0000 \rightarrow 0001 \rightarrow 1001 \rightarrow 1101 \rightarrow 1111$ however follows the rule as its color change is happening at $1101$.

Figure 2: Example of an irregular color change.

Note that the others edges in both figures have colors as well, which need to follow the same dynamic.

From Stanley (1973) the number of combinations for acyclic graphs is known with the help of the corresponding chromatic polynomial for the n-cube. Therefore it's an upper boundary, but in my understanding it vastly overestimates the number of possible combinations.

I am kind of lost and would really appreciate some help!

  • 1
    $\begingroup$ Your description of the color change rules is confusing. The way I understood it, each path out of $0000$ (I'll skip the superfluous brackets and commas) is blue to the first vertex, then had to switch to red for the rest of the way. Obviously that is a trivial problem, but it is what your description sounds like. Your example shows it isn't what you mean, but doesn't clarify to me what exactly the rules really are. $\endgroup$ Apr 30, 2021 at 1:59
  • $\begingroup$ @PaulSinclair You are right, I tried to make it more clear and added two example figures of an allowed and prohibited configuration. I hope this clarifies the rules. $\endgroup$
    – user921407
    May 4, 2021 at 14:31
  • $\begingroup$ Is it equivalent to say that (after orienting all edges in the direction of increasing-number-of-$1$s) we're coloring all the edges and, whenever an edge into a vertex $v$ is red, all edges out of $v$ must be red? $\endgroup$ May 4, 2021 at 16:30
  • $\begingroup$ @MishaLavrov Yes, that's correct and a very good description of the problem. $\endgroup$
    – user921407
    May 4, 2021 at 17:31

1 Answer 1


Not an answer, but here are some ideas that may prove useful:

  • Assign to each vertex a level equal to the number of $1$s in its coordinates. The number of vertices of level $k$ is $n\choose k$. Call the lone level $0$ vertex the bottom, and the lone level $n$ vertex the top.
  • Every edge connects two vertices whose levels differ by $1$. Direct the edges to point from the lower level to the higher level. The only way a path can get from the bottom to the top in just $n$ steps is to increase in level with every step. So your paths follow all edges in the indicated direction.
  • For a given legal coloration, call a vertex blue if every edge leading to it is blue (this includes the bottom vacuously). And call it red if every edge leading from it is red (this includes the top vacuously).
  • Every vertex in the $n$-cube must be either red, or blue, or both. If a vertex is not blue, then there is some incoming red edge. But that means every outgoing edge must be red to avoid a path changing from red to blue. Therefore any non-blue vertex must be red.
  • Call a $k$-face (a $k$-dimensional subcube) red (resp. blue), if every edge in it is red (resp. blue).
  • If a vertex of level $k$ is blue, then the $k$-face connecting the vertex to the bottom (the face "generated" by the blue vertex) has to be blue. If a level $k$ vertex is red, then the $n-k$ face connecting that vertex to the top (the face "generated" by the red vertex) has to be red. Thus every vertex is part of a face of the same color.
  • A peak blue vertex is a blue vertex whose generated face is not contained in a larger blue face. Similarly for a peak red vertex. Note that a vertex that is both red and blue must be peak for both colors.
  • Every blue vertex is either a peak vertex or else it is contained in a blue face generated by a peak vertex. And similarly for red vertices.
  • If an edge connects a blue face to a red face, it can be either color. I.e., changing its color yields another valid coloration. For any path passing through the edge, everything before the edge is in a blue face, so must be blue, and everything after the edge is in a red face, so must be red. So the edge itself can be either color without violating the restrictions.
  • If two colorations have the same peak blue vertices, and the same color for all edges connecting the generated blue faces to vertices not in any blue face (the "border edges"), then the two colorations must be the same. This is because all vertices in blue face are blue, while those that are not have to be red. All edges connecting red vertices are red, all edges connecting blue vertices are blue, and all the remaining edges are in the set hypothesized to be the same for both colorations.

Thus you can uniquely identify a coloration by its peak blue vertices and the coloring of its border edges. And any choice of peak blue vertices (chosen so none lies in the face generated by another) and any choice of colors for the border edges yields a valid coloration (setting aside your requirement that all edges at the bottom are blue and at the top are red).

But turning this into a counting algorithm is still tricky.

  • 1
    $\begingroup$ Quite a late answer, but thank you for your response! I managed to solve this problem by a brute force method for small n which was sufficient for my needs. $\endgroup$
    – user921407
    Nov 15, 2021 at 15:30

You must log in to answer this question.

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