[GAP Forum] Girth of coset graph

[David Hobby]

Erik Postma wrote:
...
>> 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 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.

Erik--

Hi.  That's the best I could do, pretty much a breadth-first
search.  In Josef's work, he has |G| much greater than
|H|*|K|, since he's trying to get a large girth.  So removing
the cosets of H that intersect with the subgroup K is not
much of a savings from just using all the cosets of H.

...
> * 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 bet it has to be, if you succeed in getting a large girth.

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

Clever.  It would increase bookkeeping costs, though.

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

I don't see this one as helping much.  You're essentially trying
to remove duplicate paths to get to a new coset.  But if you ever
DID have two different paths to get a coset, you've found a
cycle in the graph, and you're done.

One can extend the above observation to get a bound on the girth
in terms of |G|, |K| and |H|.  (Although there may well be another
way to get this.)  I'll outline it for a case that Josef was working
on:

> I have been trying
> various groups including S_n but when the group gets large gap runs out of
> memory (usually after several hours!). The best (computationally, that is,
> in terms of gap being able to work things out without crashing) results I
> got till now were, as you suggested, when H and K were cyclic generated by
> two permutations. (Sometimes I tried groups which were, say, fp groups, but
> turning them into permutation groups was often essential). But when I went
> beyond S_8 gap could not cope. However I cannot use a small group generated
> by the two permutations because I want girth 14. So I'll try your method
> with (1,2,3,4,5,6,7,8,9) and (1,2), which gap cannot tackle if I let it
> generate the whole sets of cosets. 

Here K and H would be the cyclic subgroups of G = S_n generated by the
two permutations.  I believe Josef found girth 12 using (12345678) and 
(12) in S_8.  I've been looking at this in terms of elements rather
than cosets.  For |K| and |H| small, it doesn't make much difference.

So I start at the identity, i, and look at the new elements produced.
I get (12) by using an H-coset, and then get 2*7 new elements by using
either of the two K-cosets.  Then I'll look at what I get by using
H-cosets on the last 14 elements, giving 14 more.  Etc.

I'm assuming that all the elements produced this way are new, because
if there are any repeats then we have a cycle in the graph.  But the
pigeonhole principle will eventually force repeats.  How far can we
go before this happens?  Combining H and K steps as Erik does, one
usage of H and K gives 1 + 1 + 14 = 16 elements.  I calculated the
rest by hand, so there may by mistakes.  But I got that the number
of elements goes up by around a factor of 7 each time we do H and
K cosets again, giving the sequence: 0, 16, 128, 912, 6400, 44816.
The last one is more than 8! = 40320, meaning that there must be
two products of length 10 that come out the same.  This yields a
cycle of length 20, which simplifies to one of length 18, giving
an upper bound on the girth of 18.  (By "simplifies", I mean
removing obvious extra steps from the cycle.  For instance, uses
of H and K cosets must obviously alternate.)

It's an interesting problem.

					---David