[GAP Forum] Girth of coset graph

[David Hobby]

Josef Lauri wrote:
> Hello,
> 
> Is there a good way of computing this parameter?
> 
> Let G be a finite group and H, K two subgroups whose intersection is trivial
> and whose union generates G. I need the length of the shortest sequence
> H=H_1, K=K_1, H_2, K_2, ... , K_t, H_{t+1}=H, where the H_i are cosets of H,
> K_j are cosets of K, all cosets in the sequence are distinct except for H_1
> and H_{t+1} and (this is the crucial bit), the intersection of consecutive
> cosets in the sequence is non-empty.

Josef--

Hi.  This wouldn't really use much of GAP, but how about
trying the following?  Restrict to the case where H and
K are cyclic subgroups of S_n, and let G be whatever
subgroup is generated by H \cup K.  (This doesn't feel
like you're losing too much.)  Now let h and k be the
generators of H and K respectively.  You can now view
your question as trying to find the shortest nontrivial
word in h and k that's equal to the identity.
(I believe that looking for the shortest one insures
there won't be repeated cosets.)

This is now a fairly standard computer science problem
that you'd solve by breadth-first search.  Just start
producing all the words...  Note that you can do this
by labeling all of the permutations in G by single
numbers, which signify the length (measured in number
of blocks of h's and k's) of the shortest word giving
you that permutation.  If you don't have a word yet
that gives a permutation, label it with -1, or
something.  Start with i labeled with 0, and the
rest of G labeled with -1.  Then take everything
that's labeled 0, multiply it by all powers of h,
and label all the new stuff you get with a 1.
Next take everything labeled 1, multiply by all
powers of k, and label the new things with 2s.
Continue, watching out to see if you ever get
back to i.  When you do, you can recover the
word that got you there by examining the labels,
taking a path where they decrease by 1 at each step.

(I was trying this for h = (12) and k = (123...n) a
bit by hand.)

				---David