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.