The ladder game
The ladder game is an algorithm for the stepwise determination of transversals of the sets of double cosets to for a subgroup of a group and a sequence of subgroups, a so-called ladder, of with either or for all .
We call a step from to with a step down. A double coset of and splits into double cosets of and :
for a transversal of . Therefore, a transversal of the -double cosets is a subset of where means a transversal of the -double cosets. This subset has to be determined.
A step up from to is a step with . Such double cosets of and fuse to a double coset of and :
for a transversal of . We obtain a transversal of the double cosets of and as a subset of a transversal of the double cosets of and .
To keep down the complexity of this algorithm, we should try to choose a ladder with a small index between and for all , because during each step, dow or up, respectively, we run through a transversal of and , respectively.
In order to visualize the ladder game we introduce a graph which we call orbit graph:
- The -double cosets, , correspond to the vertices of the graph.
- Two vertices are connected by an edge iff the corresponding double cosets and fulfill
- or .
Let us return to the determination of transversals of and of We need a ladder of containing and . For this purpose we take the following sequence of parabolic subgroups (generalizing this way the ladder game that we applied to designs on sets, where we took a ladder of Young subgroups!)
as a ladder. Starting from the trivial transversal of we can determine step by step all transversals of for all .
Let us display a concrete example: We take the parameters and, for we choose , the complete monomial group, which is isomorph to the wreath product . Then we get the following orbit graph:
In this graph the vertices with the labels correspond to the orbits of on the set of -supspaces of and the vertices labeled by the tuples correspond to the orbits of on the set of -subspaces.