[GAP Forum] Girth of coset graph
David Hobby
hobbyd at newpaltz.edu
Mon Jun 9 16:45:07 BST 2008
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
More information about the Forum
mailing list