Cayley graph of Rubik's cube group
up vote
1
down vote
favorite
(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 $2times2times2$ Rubik's Cube? (Is it still hard to examine the Cayley graph?)
group-theory finite-groups rubiks-cube cayley-graphs
edited Nov 17 at 14:59
Bernard
116k637108
asked Nov 17 at 14:49
giannispapav
1,474324
|
show 2 more comments
up vote
1
down vote
favorite
(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 $2times2times2$ Rubik's Cube? (Is it still hard to examine the Cayley graph?)
group-theory finite-groups rubiks-cube cayley-graphs
edited Nov 17 at 14:59
Bernard
116k637108
asked Nov 17 at 14:49
giannispapav
1,474324
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.
– Travis
Nov 17 at 20:23
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$.
– Travis
Nov 17 at 20:23
@Travis Thanks for the information! Where could I find the approach you mention on your first comment?
– giannispapav
Nov 17 at 20:33
You're welcome. See math.stackexchange.com/questions/249476/… for lots of info.
– Travis
Nov 17 at 20:47
1
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).
– Christopher Mowla
Nov 18 at 10:36
|
show 2 more comments
up vote
1
down vote
favorite
up vote
1
down vote
favorite
(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 $2times2times2$ Rubik's Cube? (Is it still hard to examine the Cayley graph?)
group-theory finite-groups rubiks-cube cayley-graphs
edited Nov 17 at 14:59
Bernard
116k637108
asked Nov 17 at 14:49
giannispapav
1,474324
(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 $2times2times2$ Rubik's Cube? (Is it still hard to examine the Cayley graph?)
group-theory finite-groups rubiks-cube cayley-graphs
group-theory finite-groups rubiks-cube cayley-graphs
edited Nov 17 at 14:59
Bernard
116k637108
asked Nov 17 at 14:49
giannispapav
1,474324
edited Nov 17 at 14:59
Bernard
116k637108
asked Nov 17 at 14:49
giannispapav
1,474324
edited Nov 17 at 14:59
Bernard
116k637108
edited Nov 17 at 14:59
Bernard
116k637108
edited Nov 17 at 14:59
Bernard
116k637108
116k637108
asked Nov 17 at 14:49
giannispapav
1,474324
asked Nov 17 at 14:49
giannispapav
1,474324
asked Nov 17 at 14:49
giannispapav
1,474324
1,474324
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.
– Travis
Nov 17 at 20:23
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$.
– Travis
Nov 17 at 20:23
@Travis Thanks for the information! Where could I find the approach you mention on your first comment?
– giannispapav
Nov 17 at 20:33
You're welcome. See math.stackexchange.com/questions/249476/… for lots of info.
– Travis
Nov 17 at 20:47
1
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).
– Christopher Mowla
Nov 18 at 10:36
|
show 2 more comments
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.
– Travis
Nov 17 at 20:23
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$.
– Travis
Nov 17 at 20:23
@Travis Thanks for the information! Where could I find the approach you mention on your first comment?
– giannispapav
Nov 17 at 20:33
You're welcome. See math.stackexchange.com/questions/249476/… for lots of info.
– Travis
Nov 17 at 20:47
1
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).
– Christopher Mowla
Nov 18 at 10:36
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.
– Travis
Nov 17 at 20:23
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.
– Travis
Nov 17 at 20:23
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$.
– Travis
Nov 17 at 20:23
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$.
– Travis
Nov 17 at 20:23
@Travis Thanks for the information! Where could I find the approach you mention on your first comment?
– giannispapav
Nov 17 at 20:33
@Travis Thanks for the information! Where could I find the approach you mention on your first comment?
– giannispapav
Nov 17 at 20:33
You're welcome. See math.stackexchange.com/questions/249476/… for lots of info.
– Travis
Nov 17 at 20:47
You're welcome. See math.stackexchange.com/questions/249476/… for lots of info.
– Travis
Nov 17 at 20:47
1
1
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).
– Christopher Mowla
Nov 18 at 10:36
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).
– Christopher Mowla
Nov 18 at 10:36
|
show 2 more comments
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3002442%2fcayley-graph-of-rubiks-cube-group%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
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.
– Travis
Nov 17 at 20:23
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$.
– Travis
Nov 17 at 20:23
@Travis Thanks for the information! Where could I find the approach you mention on your first comment?
– giannispapav
Nov 17 at 20:33
You're welcome. See math.stackexchange.com/questions/249476/… for lots of info.
– Travis
Nov 17 at 20:47
1
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).
– Christopher Mowla
Nov 18 at 10:36