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

[Richard Smith]

Philip Saddleton wrote:

> 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 turns out to be fairly obvious if you think of it in
turns of Q-sets.  The rt=tr requirement is the same as
saying r^-1.t has order 2:

  r^2 = t^2 = 1   [by definition as r, s, t are involutions]

  rt = tr   =>   (rt)^2 = rt.tr = 1   =>   | r^-1 . t | = 2

So t acts as a single to join the r-s courses, and as the
Q-set has order 2, we can necessarily join all of the r-s
courses to form an extent.

It's interesting that Knuth attributes it to Carla Savage,
and dates it as late as 1989.  The Pak - Radoicic paper
gives it as Lemma 1 and attributes it to the 1959 paper by
Rapaport.

RAS