[r-t] Decisions / Algorithms for generating the extent
Richard Smith
richard at ex-parrot.com
Fri Jun 30 09:33:03 UTC 2006
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
More information about the ringing-theory
mailing list