[GAP Forum] Girth of coset graph

[Erik Postma]

On Sat, Jun 7, 2008 at 6:03 AM, Josef Lauri <josef.lauri at um.edu.mt> wrote:
> Hello,

Hi Josef,

> 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.

I assume you also require t > 1 (otherwise the solution would always
be H, K, H).

> The way I solve this at the moment is using GRAPE. I construct the bipartite
> graph whose vertices are the cosets of H and K and in which two cosets are
> joined by an edge if their intersection is non-empty. Then I find the Girth
> of the bipartite graph. But this does not work for large groups because GAP
> runs out of memory. And it seems wasteful to construct the whole graph when
> we only want the girth and we can start with any two adjacent cosets since
> the graph is edge-transitive.
>
> Actually, what I am looking for is G, H and K for which the above girth is
> at least 14. I can go up to 12 with the above method. Also, I can relax the
> condition on H \cap K being trivial if necessary, as long as I can still get
> large girth.
>
> Thanks for any helpful comments.

I can't, off the top of my head, think of any "really clever"
algorithm that uses the group structure to its fullest. But if you
have a good algorithm for finding all H-cosets disjoint from K, the
following idea should at least use less memory than what you proposed
(although worst case it might not make much of a difference, but see
possible optimizations below) and not be much slower.

I propose to do what you propose, but only use the graph implicitly. Basic idea:
* Compute the H-cosets disjoint from K (assign to a set Hcosets) and
the K-cosets disjoint from H (assign to a set Kcosets).
* Set furthest = [K]. This will be the set of cosets at the longest
distance from H considered so far, along simple paths starting with H,
K.
* Set furthestminus1 to [H]. This will be the set of cosets at
distance one less than furthest.
* Set girth to 2.
* Loop through the following 3 bullet points:
* For all cosets K' in furthest, conjugate Hcosets into the set of
H-cosets disjoint from K'; set furthest to the union of all these
cosets, minus furthestminus1. If H is in this set, then the girth of
your graph is given by girth. Otherwise, set furthestminus1 to the old
value of furthest.
* For all cosets H' in furthest, conjugate Kcosets into the set of
K-cosets disjoint from H'; set furthest to the union of all these
cosets, minus furthestminus1. Set furthestminus1 to the old value of
furthest.
* Add 2 to girth.

You can extend this to also give you an actual cycle that has that
girth by keeping track of the path leading to every element in
furthest.

If your graph would have degree d and girth g, you'd still need to
consider d^g cosets: that should be the number of cosets in the last
stage. I can imagine a scenario where that would essentially be all
cosets in the group.

I can think of two optimizations:
* Start building from both H and K. The above algorithm start on the
"right side" of the sequence H, K and extends it only from there; you
could alternate adding a "layer" to the right and to the left. This
way, you'd only have to consider 2*d^(g/2) cosets in the last round.
* Use the group structure more cleverly: if you have the automorphism
group of the graph (which you should be able to get from the
automorphism group of the group itself I think), then you can take
advantage of that: at every stage, compute the stabilizer of each
current path, find the orbits of that stabilizer on what would be the
next set "furthest", and then take only one representative of each
orbit instead of all the elements. There will be some bookkeeping
involved in keeping track of the stabilizers, but you can of course
use the stabilizers from the previous stage to compute those for the
current one. This approach will work best if you expect your graph to
have a large automorhism group.

All the best,

Erik Postma
www.maplesoft.com