Conference rusure::math

N flips are in general required. Look at the problem backwards: given an
initial 1...N order, how many different reorderings can be produced with fewer
than N flips? It is the sum from 1 to N-1 of k!, which is less than N!. Since
N! possible orderings exist, there is at least one which cannot be produced
by fewer than N flips.

Lynn 

Yes, I forgot to mention that the problem has some interesting subtleties.

The number of orderings possible of N disks in 2 flips can be as large as
(N-1)(N-2).  For three flips, it may be as large as (N-1)(N-2)**2, for 4
flips, it may be almost as large as (N-1)(N-2)**3 (for large N).

That is, the number of possible orderings acheivable in k flips is not
simply k! or even (N-1)!/k!.  Good try.

Yes - the problem is the massive number of duplicates to count. For N=5, there
are at least 1875 ways of simply reversing all the disks in five moves.

A computer program helped somewhat.  The following table lists the number
of disks, the greatest number of flips needed, and the number of disks at
each 'distance' from the ordered disks.

	      0 1  2   3    4     5    6      7    8   9
4 disks:  (4) 1,3, 6, 11,   3
5 disks:  (5) 1,4,12, 35,  48,   20
6 disks:  (7) 1,5,20, 29, 199,  281,  133,    2
7 disks:  (8) 1,6,30,149, 543, 1357, 1903, 1016,  35
8 disks:  (9) 1,7,42,251,1191, 4281,10561,15011,8520,455
9 disks:  (?) 1,8,56,391,2278,10666,38015,...

Note that for 4 disks, there are 4! permutations of the disks, and
the 'connectivity' between these permutations forms a graph.  This
graph is quite symmetric -- from every node, the graph looks the same.

What geometric figure is formed by this graph?

Are there any other geometric figures (also with all nodes symmetric/
indistinguishable) that have the same 'adjacency' figures: 1,3,6,11,3?

The graphs so formed happen to be 'point symmetric graphs' (see note 53).

Point symmetric graphs are very similar -- that is, every point looks like
every other, even if its neighbors are considered.  Some other examples of
point symmetric graphs are cycles, complete graphs, the regular solids,
truncated forms of the regular solids (take a tetrahedron and cut off all the
corners), and multiply-truncated forms of the regular solids (take a cube, cut
off all the corners; now cut off all the corners of that), also, a cube with Xs
on opposite faces (the middle of the X is not a new point), a cube with Xs on
all faces, regular solids with complete graphs added to each face, connected
'complements' of a point symmetric graph (where theres an arc in one graph,
there's no arc in the other), projections of a point symmetric graph (for the
4-disk problem, consider two positions equivalent even tho the middle two disks
are out of order, this makes a truncated tetrahedron), the positions in a
Rubik's cube, any group of things where a set of transformations are
consistently applied (as in the case of our disks, and many other problems in
this file), and any (methinks) group with a finite set of generators. 

In note 53, I made a couple of conjectures.

    C1.	Every connected point symmetric graph of more than two points
	contains a Hamiltonian curcuit.

    C2.	Let d(i) be the number of points at distance i from a point in a
	connected point symmetric graph G.  Then the values d(i) uniquely
	determine the graph G.

Because these graphs turn up so regularly, it'd be nice if these conjectures
were true.  The second one gives us a simple way of telling whether two point
symmetric graphs are equivalent (so that a problem can be readily visualized as
being a problem on the surface of some solid, for example). 

Jerry Leichter said these conjectures stumped the graph theoreticians at Yale.
Well, they're probably less interested in recreational mathematics than we! 

With some work, we ought to be able to find all point symmetric graphs of, say,
12 nodes or less, and verify these conjectures.  That'd be interesting, and
possibly publishable, even if the conjectures are shown to be false! 

Here's the start of such a list:

    For graphs of 1, 2, 3, 4, or 5 nodes the only point symmetric graphs are
    the cycles and the complete graphs (note that, for an odd number of nodes,
    each point must have an even number of neighbors in the graph).

    For graphs of 6 nodes, there are 4 point symmetric graphs, the cycle, the
    cycle with arcs connecting opposite nodes, the complete graph, a the cycle
    with every other point also connected. 

    For graphs of 7 nodes, there are ? point symmetric graphs, the cycle, the
    complete graph, and the cycle with arcs connecting every other point in the
    cycle (this is equivalent to the graph connecting every third arc).  Are
    there any others for 7 nodes? 

Can anyone suggest a plausible algorithm for generating these?  Checking
whether a graph is point symmetric is fairly straight-forward (albeit slow):
given a nxn connectivity matrix, find n permutations of the rows and columns
that are equal to the original matrix, with each of the n different rows
permuted to the top.

					- Gilbert

Oops and ahhs.

I omitted a point symmetric graph of 6 nodes from the previous reply,
because it didn't 'look' like a point symmetric graph.  Here it is:

			*---*
		       /|   |\
		      *-+---+-*
		       \|   |/
			*---*

(it's a prism with a triangular base).  The following is also a point
symmetric graph:

			*---*
		       / \ / \
		      *---+---*
		       \ / \ /
			*---*

These two graphs are different (the second has no triangles), yet have
the same distribution of 'distances' (3 at distance 1, 2 at distance 2).
Thus, this gives a counter-example to C2.  Hurrah!

The graph for flipping 4 disks is rather strange.  Does it have a
Hamiltonian circuit?

					- Gilbert

	The "point-symmetric" graphs that come out of the disk-flipping
problem are simply the Cayley diagrams for the underlying abstract groups.

	These were introduced in Note 1089.   Briefly, a Cayley diagram
is a directed multigraph whose vertices correspond to the elements of the group 
and whose edges are coloured with the generators of the group:  there is an edge
from x to y coloured with a generator g if xg = y.

	A Cayley diagram is "point-symmetric" (or vertex-transitive as I
stubbornly prefer to call it) because any transformation of the graph of
the form x -> ax for all x, can be easily shown to be an automorphism:
	xg = y <=> axg = ay

	There exists an AM corresponding to any pair of vertices a and b,
viz: x -> (ba')x for all x, which maps a -> b.   [' denotes inverse.]   Hence
Cayley diagrams are vertex-transitive.	

	Further, finite Cayley diagrams must be Hamiltonian, by simple 
induction on the number of generators.   (another Cayley-Hamilton Theorem? :-)

	So that tidies up the Note 53 red herring.   The question is: can we
solve the interesting question that Peter asked concerning the maximum
distance of any n-disk ordering from the start position?

Regards,
Andrew

(1) Retraction:

	My glib proof by blatant assertion of the new Cayley-Hamilton
Theorem (Cayley graphs are Hamiltonian) I no longer believe.   Everything
else in .7 I stand by.

	Note that the non-Hamiloneity of the Petersen graph has nothing to
do with .7, because Petersen is not a Cayley graph.

	When I have time, I will study a relevant text I have:  algebraic
graph theory by Norman L. Biggs (Cambridge University Press) which addresses
many of these issues.


(2) For the stacks, a result.

.1>	Does a stack of N disks always require at least N flips to order some
.1>	jumbled stack?

	Yes, for n > 2.

	Our jumbled stack contains initially n-1 bonds, each between
an adjacent pair of disks.   Each flip will destroy one bond, and create
one bond.   What we want are the good bonds, or James Bonds, which are each
of the form i <-> (i+1).   If we start off with *no* James Bond, then it
will take us at least n-1 flips to create them all.   But moreover, if the
last disk is not n itself, we will need at least one flip which reverse the
entire stack, and such a flip does not crate or destroy any bonds.   So at
least n would be required.

	The question is, does a stack exist which contains no James Bonds?
For n = 3, the answer is no (Doctor No? :-) but 132 uniquely requires 3 flips 
to order it anyway.   For n = 4, 2413 (or its reverse) satisfy the requirements.

	For n >= 5, it is sufficient to show that the dual of the cyclic graph
on n vertices is Hamiltonian, because then we can take such a Hamiltonian
cycle, and break it at some point to give our stack order (avoiding n in last
place, of course.)

	One sufficient condition for Hamiltoneity of this graph is that there 
exists q satisfying 1 < q < n-1, such that (q,n) = 1.   If n is odd, then 
q = 2 does the job.   If n is 0 mod 4, then consider q = n/2 - 1.   Here:
	(q,n) = (q,2q+2) = (q,2) = 1, since q is odd.
	If n is 2 mod 4, and n > 6 then set q = n/2 - 2.
	(q,n) = (q,2q+4) = (q,4) = 1, since q is odd.

	It remains only to treat the case of n = 6.   With obvious numbering,
(136425) is a Hamiltonian cycle in the dual of C_n (ironically this graph is
exactly the triangular prism from .6!)

Regards,
Andrew.

	I am convinced that the way forward with this question is to
tackle what on the surface seems to be a much harder problem.   Namely:
suppose that we not only require the disks to be in the right order, but
we also want (some or all of) them to be the right way up.

	Why is this important?   If we have created some James Bonds, and
we do not want to break them up, then the substack will behave like a single
orientable disk.   In fact, we may be able to show that it is never 
profitable to split a substack.

	Note that the rotation of the top disk now actually does something
useful.

	I don't have time to chase this up at the moment, but I'm sure that
it's the way forward.

Regards,
Andrew.

    The following is a citation to a paper about this problem.  The
    complete note from which this was extracted may be found at 1539.2.

				    Topher
------------------------------------------------------------------------------
From: kece@eecs.ucdavis.edu (John Kececioglu)
Newsgroups: sci.math.research
Subject: Generating a permutation by reversals (SUMMARY)

	    ...

	William H. Gates and Christos H. Papadimitriou,
	"Bounds for sorting by prefix reversal,"
	Discrete Mathematics 27 (1979) 47-57.

	 ...

The ... paper considers sorting where the operation is to reverse a prefix,
and gives upper and lower bounds of (5n + 5)/3 and 17n/16.

>	My glib proof by blatant assertion of the new Cayley-Hamilton
>Theorem (Cayley graphs are Hamiltonian) I no longer believe.   Everything
>else in .7 I stand by.

	Curiously enough, I was reading something about this just the other
day. Erdos + Somebody have studied the groups Z_x * Z_y, generated by (1,0)
and (0,1), to find necessary & sufficient conditions that the Cayley graph
is Hamiltonian. It's perhaps an interesting puzzle for this notesfile. I
don't know the answer.


Love & kisses,
Andrew.