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 be 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.

[11, 261, 9694, 502110, 33064966, 2642657228]
  • 2
    $\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 '18 at 12:03
  • $\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$ – Moritz Firsching May 21 '18 at 19:07

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.