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
_______________________________________________
Forum mailing list
[email protected]
http://mail.gap-system.org/mailman/listinfo/forum
