Number of hypercube unfoldings

Question

While writing the code for this answer, I noticed that I not only could calculate the number of unfoldings of the $4$-cube, but also the number of the $n$-cube for more values of $n$. Basically, we count pairs $(T, P)$, where $T$ is a tree on $2n$ nodes and $P$ is a perfect matching of the complement of $P$. We consider $(T, P)$ equivalent to $(T', P')$ if there is an automorphism $\phi$ of $T$, such that $T=\phi(T)=T'$ and $\phi(P) = P'$.

Here's what I found: $$\begin{array}{c|cccccc}n&3&4&5&6&7&8\\\hline \text{# of unfoldings} &11& 261& 9694& 502110& 33064966& 2642657228\end{array}$$ For $n=7$ the calculation took about $7$ hours on a desktop pc with 8 cores. The calculation can almost trivially be parallelized, since we can consider each tree $T$ at the same time. The case $n=8$ was done on a small cluster.

Have these unfoldings been counted before?

The sequence is in the oeis: A091159, but only two terms are given (as of today). I searched for the number $33064966$ on the net but couldn't find anything.

Update: Improving the algorithm to generate hypercube unfodings, together with Luca Versari, we were able to also calculate the number of unfoldings of the $n$-cube for $n=9$ and $n=10$. The code for that can be found here:  https://github.com/google-research/google-research/tree/master/cube_unfoldings

dimension	number of unfoldings	file
2	1	2.cnt.txt
3	11	3.cnt.txt
4	261	4.cnt.txt
5	9694	5.cnt.txt
6	502110	6.cnt.txt
7	33064966	7.cnt.txt
8	2642657228	8.cnt.txt
9	248639631948	9.cnt.txt
10	26941775019280	10.cnt.txt

Might there be a better approach in getting these numbers? There is a nice generating function for unlabelled unrooted trees, so perhaps a generating approach could help here too?

Matt Parker made a video about these hypercube unfoldings.

[1, 11, 261, 9694, 502110, 33064966, 2642657228, 248639631948, 26941775019280]

Answer 1

Following up on the comments about using spanning trees and automorphism groups. It does seem to me that perhaps the best way to do this would be to compute the number of different spanning trees of the hyperoctahedral graph up to symmetries of the hyperoctahedron. As Peter Taylor and Brendan McKay have noted, one can use Burnside's lemma to do this. I think this will be easier, because it seems likely that about half of all symmetries will not fix any spanning trees (see below), and that most spanning trees are not fixed by any symmetry. If this is true, most of the computation would be finding a small number of spanning trees that are fixed by reflections of the hyperoctohedron. On the other hand, it seems like computing the number of trees with an appropriate pairing would require solving several instances of the graph isomorphism problem to make sure you aren't overcounting.

The rest of this post is not about computation, but rather about general conjectures. I think (tho I haven't sat down to prove) that rotations will never fix a spanning tree. If this is so, then, after counting the number of spanning trees of the hyperoctohedral graph (which can be done using the matrix-tree theorem), we could use a very simple version of Burnside's lemma to get bounds on the number of nets. Specifically, let $N_d$ be the number of nets of the hypercube in $\mathbf{R}^d$, and let $F(d) = \frac{(2d)^{d-2} (d-1)^d}{d!}$ (this is the same number that Brendan mentions). Then, assuming (as I believe) that no rotation fixes a spanning tree, we get that

$F(d) \leq N_d \leq 2F(d).$

For some small $d$, the bounds look like this:

$d$	Bounds
2	$\frac{1}{2} \leq 1 \leq 1$
3	$8 \leq 11 \leq 16$
4	$216 \leq 261 \leq 432$
5	$8533\frac{1}{3} \leq 9694 \leq 17066\frac{2}{3}$

The table makes it look like the lower bound is probably closer to the truth. Looking at the ratios $N_d/F(d)$ for the numbers you've computed, Brendan says they appear to be going to 1. I'm a little less sure, since it looks like the rate at which they decrease is going down as $d$ increases, but with such a small dataset it's hard to tell. I'd guess that $N_d/F(d)$ approaches a constant near $1.08$. If it turns out I'm wrong, at least I'll have Legendre to keep me company.

Update: So I started being a little more sophisticated and factoring in what to me are the most obvious symmetries that fix some spanning trees – reflections that interchange only two opposite points. Let the number of spanning trees of the hyperoctohedron in $\mathbf{R}^d$ be $T_d$. Then we can choose a pair of opposite points in $d$ ways. For a spanning tree to be fixed by this reflection, these opposite vertices must both connect to the same vertex, and in order for it to be a tree they can only connect to a single vertex, and we can choose that vertex in $(2d-2)$ ways. Finally, we need a spanning tree of the rest of the hyperoctohedron, but that's actually the same as a spanning tree of the $d-1$ octohedron. So the number of trees fixed by one of these reflections is $(2d-2)T_d$, and there are $d$ such reflections. When we factor this into our lower bound we get $N_d \geq F(d) + (d-1)F(d-1)$.

This is enough to show that $N_d/F(d)$ does not approach 1, since

$\frac{N_d}{F(d)} \geq \frac{F(d) + (d-1)F(d-1)}{F(d)} \xrightarrow{x\to\infty} 1 + \frac{1}{2e^2}.$

I think there's still one more class of reflections contributing a significant number of fixed spanning trees. I'll update as soon as I find it. Right now my prediction for $N_{11}$ is $3.30\times 10^{15}$.

Update: I realized this construction can be extended a little bit. After you fix two opposite vertices and remove them, you're looking at a hyperoctohedron in $\mathbf{R}^{d-1}$. Now, instead of just taking any spanning tree, you can take a spanning tree and an automorphism fixing that spanning tree $\sigma$. If you let $\alpha$ be the automorphism reflecting the two opposite vertices we chose, then you can connect up your two chosen vertices to the chosen tree, and then you get that the whole thing is fixed by $\sigma \circ \alpha$.

I haven't taken the time to work this into the lower bound. However, it does show that my initial conjecture that no rotation fixes a spanning tree is off, which means there's a more subtle reason why certain automorphisms cannot fix a spanning tree.

I think that if you're careful enough, then doing this construction with spanning forests on the $d-1$ hyperoctohedron, and then connecting the forest into a tree with your two chosen vertices, should exhaust all the possibilities when $d$ is odd. When $d$ is even I think there's going to be special spanning trees that don't fit this construction.

Update: I think actually there's actually a better repair than the one I mentioned above. The graph we're considering can actually be thought of as two complete graphs $K_d$ connected up in a certain way. So, you have several symmetries that flop two copies of $K_d$. If you fix one of these symmetries, you can get trees which are fixed by this symmetry by the following recipe:

1. Choose a rooted spanning tree for $K^d$.
2. Connect the two copies of $K^d$ by an edge between the two roots.

It seems like understanding the exact count of these spanning trees is going to involve understanding automorphisms of rooted trees on $d$ vertices. As far as I can tell, there is no closed form solution for this problem, but perhaps there are good enough asymptotics on the rooted tree problem to give good asymptotics for the problem of nets of cubes.