# Message #1842

From: David Vanderschel <DvdS@Austin.RR.com>

Subject: Re: [MC4D] State graph of MC2D

Date: Wed, 03 Aug 2011 17:16:49 -0500

Nan wrote:

>I haven’t read your CLS stuff yet. But about Melinda’s

>classification of the 24 states, here is my understanding:

>Her definition of equivalency is not the conjugate

>class. It’s about global rotation and re-coloring.

>Definition: Starting from state A, if there exists a global

>rotation of 90*n degrees affecting all the corners and the

>centers, and then exists a recoloring (a permutation of the

>four colors), resulting in state B, then we say state A and

>state B are equivalent.

OK. The above can be rephrased in terms of conjugation, and

I should have seen the way earlier. You are saying that 2

pemutations are related if one is a conjugate of the other

by 4-cycle that may be perceived as a rotation relative to

the corner positions in the puzzle. That does rule out the

4-cycles for which a cubie is crossing to the diagonally

opposite position. However, this would split node 5 into 2

subsets depending the direction of the rotation. I.e., I

see 3-cycle patterns that cannot match up with the canonical

pattern for state 5 without also mirroring them. If

4-cycles with diagonal crossings were admitted, then state 5

would remain intact. However, the regular conjugacy classes

would then merge. So I think something is still missing

from the explanation.

When I speak of "mirroring", I am not talking about moving

the face pieces. I actually ignore them. I am just talking

about a permutation of the cubies. Reflecting about a

diagonal axis would correspond to a 2-cycle for the two

cubies not on the axis. Reflecting about a coordinate axis

corresponds to two 2-cycles one for each pair of cubies with

the same coordinate on the axis about which we are

reflecting.

Melinda wrote:

>I haven’t given your message a careful read yet, and the

>meat of it seems to introduce some interesting ideas, but

>since you claim to be confused by my diagram, I thought I

>would reply briefly and see whether I can’t make it

>clear. First off, maybe I shouldn’t call it a state graph

>as Nan suggests. He suggests the word "type" instead but

>that feels too general a term for this purpose but is

>probably better than "state".

Clearly, each node in the diagram does correspond to one of

the sets in a partition of the permutations of S4.

Furthermore, we can say that there is an edge between two

such nodes if, given a permutation in one set, there exists

a permutation in the other set which differs by a single

twist relative to the position indexing implied by the

puzzle and the allowed 2-cycles. That much should have been

clear all along.

What I am trying to get hold of is the relation which

determines the partitioning. I suggested, "Two permutations

are related if they are conjugates and, if one moves a cubie

to the diagonally opposite corner, then both must do so." I

believe that relation does correctly determine your

partitioning. Since conjugacy is so easy to check (based on

cycle structure), interpreting the above relation (strange

as it may seem) is much easier than interpreting your or

Nan’s attempts to describe the rule for the partitioning.

If it is not clear what I am concerned with, check out

http://en.wikipedia.org/wiki/Partition_of_a_set#Partitions_and_equivalence_relations

or http://preview.tinyurl.com/3u6tzeh

Partitions of a set and equivalence relations on the set

are equivalent concepts. I see the partitioning. I am

trying to figure out a nice way to state the corresponding

equivalence relation. I am also biased to try to find

such a description in terms of the permutations themselves

and not in terms of manipulating an abstract physical

model in 2-space or 3-space. (As we have already

experienced, the latter type of description is difficult to

make precise in a mathematical sense.)

>What the diagram really represents is a "map" in the

>ordinary geographic sense. (Not the graph-theoretic

>one).

I am sorry, but I just don’t get this analogy. There is no

way I can see that this mapping of permutations to nodes in

2-space admits geographic interpretation. It is still a

graph in the sense that there are nodes connected by edges.

The nodes of this graph correspond to sets in a partition of

S4.

>Given a scrambled state and this map you would start by

>finding the node who’s pattern exactly matches the

>scrambled state.

"exactly matches" is not well defined. Nan suggested

rotations, but I saw that mirroring was required to keep

state 5 intact. If reflection about a diagonal axis were

admitted, you’d be back to conjugacy classes. Thus any such

mirroring must be restricted to reflections in the

coordinate axes, which are even permutations (crosses).

>There will be exactly one such node though you may need to

>rotate the map to match the scramble pattern, and/or swap

>some colors, but you will find it. For example, Next you

>select a path from that node to the solved "pattern". God’s

>algorithm simply selects one of the shortest such

>path. Finally, you look at each transition from your

>current pattern to the next one in your chosen path which

>will correspond to exactly one twist. Just follow the path

>and you’re done.

But it’s not that hard in the first place:

```
Whenever any cubie is diagonally displaced, then, to get<br>
a shortest solution, you must immediately do a twist<br>
that moves at least one such diagonally displaced cubie.<br>
For such a diagonally displaced cubie, there are two<br>
slices you can twist. If twisting one of them will<br>
place the other cubie in it, twist that slice. If<br>
twisting one of them will displace the other cubie from<br>
its home position and twisting the other slice won't do<br>
that, twist the other. When no cubie is diagonally<br>
displaced, the solution is obvious.
```

The preceding rule is much easier to understand and act upon

than trying to find your place in the diagram and thinking

about which member of the next node in the path is one that

you can get to with a single twist. (The last part is

referring to the fact that it is not true that _any_ pair of

permutations from adjacent nodes differ by a single twist.)

>I called node 5 a bottleneck because any solution path from

>the maximally distant nodes 6 and 7 must funnel through

>that node. I certainly meant it no disrespect and trust it

>does not feel maligned. :-)

Calling it anything would seem to imply that there is some

associated signficance. I am at a loss to discern any such

significance. To get, with a single twist, from either of

states 6 or 7, both of which are odd, you have no choice but

to go to an even permutation, and it won’t be a cross. The

3-cycles are all that’s left among the even permutations.

So what? If there is any point to be made, I think it is

that, since partition set 5 is so large (including 2/3 of

the even permutations), it is bound to be central in the

sense that you can reach it with a single twist from any odd

permutation; but I still don’t see actionable information

here.

>So you see, the map has a definite and useful purpose, just

>maybe not the one that you were expecting.

I am not sure that it is appropriate to call it "useful"

when the problem it solves admits a solution that is so much

simpler to describe and implement. To make a utility

argument, I think you would have to move the considerations

into a purely academic domain. However, for that to be

interesting, I think the approach would have to generalize

to more complex puzzles. Using pure conjugacy classes, I

have already shown a way to do that. So let’s talk about that

approach.

Regards,

David V.