[GAP Forum] Girth of coset graph

[Josef Lauri]

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.

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.

Josef Lauri
Department of Mathematics
University of Malta