[r-t] Decisions / Algorithms for generating the extent
Philip Saddleton
pabs at cantab.net
Thu Jun 29 21:03:31 UTC 2006
Richard Smith said on 26/06/2006 15:00:
> The idea of apply Plain Changes to the coursing order is
> given in Knuth's "The Art of Computer Programming"
>
> <http://www.ex-parrot.com/~richard/papers/fasc2b.ps>.
>
> as Exercise 69 on page 32, and attributed (page 48) to E.S.
> Rapaport [Scripta Math. 24 (1959), pp51-8]. I've not
> managed to lay my hands on a copy of this paper, though it
> seems to be cited quite frequently. (Interestingly,
> Rapaport is quoted as being "particularly motivated by bell
> ringing". Does anyone know anything about this person?
> Were/are they a ringer?)
>
Knuth also mentions
a more general fact observed by Carla Savage in 1989, namely that the
Cayley graph for any group generated by three involutions r, s, t has a
Hamiltonian circuit when pt=tp [see I. Pak and R.Radoicic, "Hamiltonian
Expanders," to appear].
This paper is on the web at
http://www-math.mit.edu/~pak/hamcayley8.pdf
This considers the classical Lovasz conjecture, that every connected
Cayley graph is Hamiltonian (nb this does not include digraphs - viz
Thompson or Rankin). There is some interesting stuff here, including the
historical remarks:
It seems that the problem of finding Hamiltonian cycles in Cayley graphs
was suggested for the first time by Rapaport-Strasser. She was motivated
by bell ringing ...
see also
http://en.wikipedia.org/wiki/Lov%C3%A1sz_conjecture
--
Regards
Philip
http://www.saddleton.freeuk.com/
More information about the ringing-theory
mailing list