2
$\begingroup$

(a) I would like to know whether there is a group theoretic approach for calculating the diameter of the Cayley graph of Rubik's Cube group.

I know it's been proved that the above diameter is $20$ but the approach uses brute force.

Also I wonder whether there is a "nice" presentation of this group (it is a finite group so the relations between the elements of this group come from the multiplication table, but (b) is there a systematic way of writing down these relations?)

What about a $2\times2\times2$ Rubik's Cube? (Is it still hard to examine the Cayley graph?)

EDIT

Since there has been no full answer to my initial questions I'd like to ask for something else too:

Is there an "nice" way to describe a maximal tree of the Cayley graph of the $3\times3\times3$ Rubik's Cube?

$\endgroup$
  • $\begingroup$ There is certainly a group-theoretic approach for calculating the diameter, and that's what the (2013?) proof of the diameter-20 result uses. While that result relies on a massive amount of case checking, it also uses clever reductions to bring it within reach of supercomputers. I don't know a "nice" presentation of the group, but GAP returns a presentation with $6$ generators and perhaps $\sim 300$ relations. It's not terribly illuminating to look at, though. $\endgroup$ – Travis Willse Nov 17 '18 at 20:23
  • $\begingroup$ The pocket ($2 \times 2 \times 2$) cube has a relatively tractable symmetry group, $\Bbb Z_3^7 \rightthreetimes S_8$, but this still has order $3^7 \cdot 8! \sim 8.8 \cdot 10^7$. $\endgroup$ – Travis Willse Nov 17 '18 at 20:23
  • $\begingroup$ @Travis Thanks for the information! Where could I find the approach you mention on your first comment? $\endgroup$ – Γιάννης Παπαβασιλείου Nov 17 '18 at 20:33
  • 1
    $\begingroup$ I meant the 3x3x3 cube (whose moving parts are technically just corners and edges, as we can imagine the centers staying fixed). For the 2x2x2 (which obviously is just made up of corners), it would be just 1002. But we technically can imagine that one corner stays fixed when solving a 2x2x2, so it would only be 688. But yet, since I only represented the even permutations, then (in theory) it would be around double that for the 2x2x2 (or about 1400). $\endgroup$ – Christopher Mowla Nov 18 '18 at 10:36
  • 1
    $\begingroup$ As for a spanning tree, there is a Hamiltonian circuit ( bruce.cubing.net/index.html ). By removing one edge you trivially get a spanning tree. It is however not easy to describe. I doubt that there is an easy-to-decribe spanning tree. If you had one, it would also lead to an easy-to-describe solution method where there would never be any cancelling moves. $\endgroup$ – Jaap Scherphuis Dec 19 '18 at 16:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.