[r-t] Decisions / Algorithms for generating the extent
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"
> 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
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
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 ...
More information about the ringing-theory