Timeline for Number of hypercube unfoldings
Current License: CC BY-SA 4.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 19, 2021 at 15:13 | history | protected | CommunityBot | ||
| May 16, 2021 at 19:45 | answer | added | Ivan Aidun | timeline score: 6 | |
| May 16, 2021 at 2:01 | comment | added | Brendan McKay | And, still being vague, if there is a way to count labelled foldings with given symmetry, one could use Burnside's Lemma to get the number of equivalence classes. | |
| May 16, 2021 at 1:59 | comment | added | Brendan McKay | It looks like the ratio of distinct foldings to (spanning tree)/(automorphism group) is tending to 1, which would mean that the asymptotic number is $n^{n-2}(n-1)^n 2^n/(4 n!)$. To prove that one would need to show that most foldings have no symmetries, or something like that (I have to be vague because I didn't check the precise relationship between the foldings and the trees). | |
| May 15, 2021 at 21:07 | comment | added | Peter Taylor | @BrendanMcKay, my bad: for "hypercube graph" substitute "hyperoctahedral graph". | |
| May 15, 2021 at 18:52 | comment | added | Moritz Firsching |
@PeterTaylor That's cool. @Brendan McKay: unless I misunderstood something, the lower bound you describe is indeed smaller than the exact values: [(4, 8, 0.5), (384, 48, 8), (82944, 384, 216), (32768000, 3840, 8533.3...), (20736000000, 46080, 450000)] . Here I have (spanning tree count, order of Aut, fraction of those) starting from dimension 2. They seem to be indeed always smaller. I wonder if this can be used to count them more efficiently..
|
|
| May 15, 2021 at 15:50 | comment | added | Troy | Someone in Matt Parker's video pointed out that these are very similar to tetrominoes and their sequences maybe there is a parallel in a simpler calculation there? Looking through the OEIS for sequences related to tetrominoes certainly seems to have patterns but might just be the mind playing tricks A230031 has the most promise imo. For the full list of sequences i looked at i mainly just searched "oeis tetromino sequences". | |
| May 15, 2021 at 13:29 | comment | added | Brendan McKay | @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. | |
| May 15, 2021 at 13:07 | comment | added | Peter Taylor | 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. | |
| May 15, 2021 at 10:09 | comment | added | Esteban Fernández Aalbau | I have tried with a Spreadsheet, the nearest formula is $$ \frac{(d!)^{2.25}}{4.887} $$ where $d$ is the dimension. The results are: 0.97 11.53 261.00 9757.08 549743.65 43815806.59 4716103000.61 661650930873.47 117660022700538.00 I have also tried: $$ \frac{(d!)^{2.24}}{4.685},\qquad \frac{(d!)^{2.23}}{4.58} \quad\text{and}\quad \frac{(d!)^{2.22}}{4.4} $$ There is a big error but maybe that is a begining. | |
| May 14, 2021 at 20:13 | history | edited | Moritz Firsching | CC BY-SA 4.0 |
added two numbers to sequence
|
| Jun 22, 2018 at 8:55 | history | edited | Moritz Firsching | CC BY-SA 4.0 |
added one more term
|
| May 21, 2018 at 19:07 | comment | added | Moritz Firsching | @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... | |
| May 21, 2018 at 12:03 | comment | added | fedja | 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 :-) ). | |
| May 21, 2018 at 11:50 | history | asked | Moritz Firsching | CC BY-SA 4.0 |