25
$\begingroup$

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]
$\endgroup$
10
  • 4
    $\begingroup$ Searching for 502110 yields some results (if you filter out postal zip-codes): lews-garage.org/unfolding-the-6-cube, for instance, with the date stamp of May 2015 (unless that is you :-) ). $\endgroup$
    – fedja
    May 21, 2018 at 12:03
  • 3
    $\begingroup$ @fedja that's a cool blog post (it is not by me)! I am glad to see that the numbers agree, which is of course an artifact of the method of finding the post... $\endgroup$ May 21, 2018 at 19:07
  • 2
    $\begingroup$ From the main result of DeSplinter et. al., Nets of higher-dimensional cubes it follows that an alternative formulation of the problem is counting spanning trees of the hypercube graph modulo its automorphism group. $\endgroup$ May 15, 2021 at 13:07
  • 1
    $\begingroup$ @PeterTaylor That would give a lower bound of the number of spanning trees divided by the automorphism group size, no? That seems to grow much faster than Moritz' list. $\endgroup$ May 15, 2021 at 13:29
  • 1
    $\begingroup$ @BrendanMcKay, my bad: for "hypercube graph" substitute "hyperoctahedral graph". $\endgroup$ May 15, 2021 at 21:07

1 Answer 1

6
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ My money is still on a limit of 1 since the numbers are still small and it is highly unusual for this type of limit to be anything except 0 or 1. It would be nice to prove an exception, though. Try dividing the ratio by $1+1/n$, which doesn't change the limit but flattens the values a lot; I think you'll agree that 1 is looking good. $\endgroup$ May 17, 2021 at 2:18
  • $\begingroup$ That's cool! I was aware that the largest fixset of spanning trees has size $T_d(d-1)2$. If we look at the list (size of fixset, #elements in Aut with that size), we have for $d=3$ the list $[(16, 9), (384, 1)]$ and for $d=4$ the list $[(8, 24), (288, 12), (96, 12), (16, 12), (192, 12), (128, 6), (2304, 4), (82944, 1)]$. Those then give the exact number via Burnside after dividing by $48$ and $384$ resp. $\endgroup$ May 17, 2021 at 18:32
  • 3
    $\begingroup$ "I think (tho I haven't sat down to prove) that rotations will never fix a spanning tree." Counterexample when $d=5$: edge set $\{(-x,+z), (-y,+x), (-z,+y), (-v,-x), (-v,-y), (-v,-z), (-v,-w), (-w,+v), (+v,+w)\}$ is fixed by rotations which permute $(x, y, z)$. $\endgroup$ May 18, 2021 at 20:28
  • 1
    $\begingroup$ I also agree that the real conjecture is probably something about compositions of reflections, since that's what my constructions look like so far. $\endgroup$
    – Ivan Aidun
    May 18, 2021 at 20:46
  • 1
    $\begingroup$ Note the following post which suggests that the ratio $N_d/F(d)$ tends to $c=e^{(e^{-2}+e^{-4})/2}\approx 1.07985$. It also contains the list of first 100 values. postchimpblog.wordpress.com/2022/05/29/… $\endgroup$ Apr 19, 2023 at 14:22

Not the answer you're looking for? Browse other questions tagged or ask your own question.