[r-t] Decisions / Algorithms for generating the extent

[Philip Saddleton]

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/