Graph Theory

[Tim Reynolds]

Consider the uncolored, undirected Cayley graph of the Rubik's Cube group with generators <R, R', R2, U, U', U2,...>. What is the chromatic number of this graph?

Here's the version of this problem that's not so terminology-heavy:
When I talk about a graph, I'm referring to this: http://en.wikipedia.org/wiki/Graph_theory

Let's say that we make a graph of all the Rubik's Cube positions and connect any two positions if they differ by a single face turn (any of R, R', R2,...). Now we color all the positions in such a way that no two connected positions are the same color. What's the smallest number of colors we need to do this?


We can set an easy upper bound of 19; it's a fairly simple result in graph theory that the chromatic number of a graph is at most the maximal degree of a vertex (18 in this case--each vertex is connected to 18 others) plus 1. A lower bound is 4--each of the positions {solved, U, U', U2} is connected to one another. Do 4 colors suffice though?

This question is equivalent to: is there some 4-state property of cube positions such that any quarter or half turn changes its value?

 

[Herbert Kociemba]

Consider the uncolored, undirected Cayley graph of the Rubik's Cube group with generators <R, R', R2, U, U', U2,...>. What is the chromatic number of this graph?


This question is equivalent to: is there some 4-state property of cube positions such that any quarter or half turn changes its value?

What do you think about the total twist of all center pieces mod 4? At least this works for the supergroup with marked center pieces.

 

[Stefan]

For an extra riddle, consider the quarter-turn version.

 

[peterbat]

For fun, I made a crude drawing on my whiteboard of the states accessible via <U,D> from the solved state (any dot in the middle black square). Here is a link to a larger photo of it.

A "coloring" scheme (labeled "A, B, C, D") is drawn that works with all the cliques in the graph.

I thought about this for 20 minutes and didn't come up with a proof, but I "feel" like 4 should work. I don't know any graph theory to speak of, but it seems like if the maximal clique size is 4, and if the cliques don't "wrap around" one another in such a way as to create a parity error (like you would get if you tried to color a 5-node ring-structure, like a bracelet with 5 beads, with a 2-color scheme), then you only need 4 colors. It "feels" like the maximal clique size is 4, based on this picture (I figured I'd get the most connectivity out of <U,D>, for example, because U and D commute).

So in other words, my math skills are too underdeveloped for this problem, but it's fun to think about .

 

[AvGalen]

Interesting question, but way to mathy for me. If you could translate this into a practical use question I will attempt this

 

[cmhardw]

The graph has an even number of vertices: 43 252003 274489 856000 to be exact.
Every vertex has degree 18
The graph is not bipartite because of double turns

Do we actually have a proof or know that a Hamiltonian Cycle exists? I know it's a goofy question, but does a "Devil's Algorithm" in fact exist? Can we prove this or disprove it?

--edit--
:fp
I thought we were looking at the 2 generator group, just saw the ellipses. Fixed the previous version of my post.

Chris

[temporary thread hijack]
When I misinterpreted the question, it led me to another interesting question that does not deserve it's own thread. Is it possible to come up with a sub-group of the Rubik's cube that has a larger diameter than the Rubik's cube group? I of course mean the diameter of the Cayley graphs of both groups.

I'm tempted to say no, but I can imagine creating rings of positions that are fairly long chains. This seems that it could make a larger diameter, but can we make such a ring be an actual subgroup of the Rubik's cube group?
[/temporary thread hijack]

 

[Tim Reynolds]

What do you think about the total twist of all center pieces mod 4? At least this works for the supergroup with marked center pieces.

That unfortunately won't work for the non-supercube group, as R L U2 R' L' U R L U2 R' L' U is an identity which affects the total twist of all center pieces. That would have been very nice though.

I thought about this for 20 minutes and didn't come up with a proof, but I "feel" like 4 should work. I don't know any graph theory to speak of, but it seems like if the maximal clique size is 4, and if the cliques don't "wrap around" one another in such a way as to create a parity error (like you would get if you tried to color a 5-node ring-structure, like a bracelet with 5 beads, with a 2-color scheme), then you only need 4 colors. It "feels" like the maximal clique size is 4, based on this picture (I figured I'd get the most connectivity out of <U,D>, for example, because U and D commute).

So in other words, my math skills are too underdeveloped for this problem, but it's fun to think about .

My sentiments exactly. I'm sure that the maximal clique size is in fact 4, but I'm not sure how rigorous the "wrapping around" thing is.

[temporary thread hijack]
When I misinterpreted the question, it led me to another interesting question that does not deserve it's own thread. Is it possible to come up with a sub-group of the Rubik's cube that has a larger diameter than the Rubik's cube group? I of course mean the diameter of the Cayley graphs of both groups.

I'm tempted to say no, but I can imagine creating rings of positions that are fairly long chains. This seems that it could make a larger diameter, but can we make such a ring be an actual subgroup of the Rubik's cube group?
[/temporary thread hijack]

Well, just for the Rubik's Cube group you can probably come up with a set of generators that gives a pretty high diameter. If we're limiting ourselves to one-HTM generators, I'm not quite sure.

 

[Stefan]

Is it possible to come up with a sub-group of the Rubik's cube that has a larger diameter than the Rubik's cube group?

I'm not 100% sure my answer is valid, but I think the group generated by <UR> is an example and has diameter 52.

 

[Herbert Kociemba]

Is it possible to come up with a sub-group of the Rubik's cube that has a larger diameter than the Rubik's cube group?

I'm not 100% sure my answer is valid, but I think the group generated by <UR> is an example and has diameter 52.

<RU2D'BD'> generates a cyclic subgroup of the maximal possible order 1260, so it has diameter 630.

 

[rokicki]

So far I have a seven-coloring (on paper). Still working on reducing this. Can anyone think of the seven-coloring I have in mind?

 

[Stefan]

Can anyone think of the seven-coloring I have in mind?

Assign a color to each corner piece. Assign a color to each cube state according to the corner diagonally opposite to the white/red/green corner.

 

[rokicki]

Can anyone think of the seven-coloring I have in mind?

Assign a color to each corner piece. Assign a color to each cube state according to the corner diagonally opposite to the white/red/green corner.

Very good. Now, how about a paper six-coloring?

 

[Stefan]

Now, how about a paper six-coloring?

You got one?

 

[rokicki]

Yessir. I'd be happy to "spoil" it but it's more fun to see what people can come up with. Maybe someone can beat me to five or four.

 

[rokicki]

Finally got a simple paper proof of four. Anyone else?

 

[Tim Reynolds]

Hmm, I'm not past seven yet, but in the mean time I challenge you to the same question applied to megaminx.

 

[rokicki]

Megaminx

Megaminx? Much harder, I think. Clearly somewhere in 5..61. I've managed to find a coloring with 19 colors, but nothing less than that yet.

 

[Stefan]

Finally got a simple paper proof of four. Anyone else?

Yes, finally I got one.

Spoiler

Assign some order to the corners. Using corner permutation parity for 2-coloring is pretty good already - every quarter turn changes the color. Only half turns are problematic because they keep the parity and thus the color. So consider the permutation parity of the corners at UFL, UBR, DFR and DBL. Every half turn does one swap to these four places. Now... simply take the combination of those two parities for coloring. Then any quarter turn changes the color because of the first parity, and any half turn changes the color because of the second parity.

Same as yours, Tom?

 

[rokicki]

Yep, Stefan, same as mine.

Megaminx, now, that's a bit trickier.