How to find the orbits of a subgroup?

[metalhadi]

Homework Statement

Hi everyone. I have just joined the community, and I really appreciate your help. Here is what I'm struggling with:

Assume a permutation group G generated by set S, i.e., G=<S>. Since S is given, we can easily find the orbit partition for G. Now assume the subgroup H of G that fixes one point in the permutation group. Can we easily find the orbit partition of H?

Let me give you an example:
Imagine group G with generators g1 = (1, 2)(3,4) and g2 = (2,5)(3,4). The orbit partition for G is {{1,2,5}, {3,4}}. Now imagine the subgroup H of G that fixes 3. What is the orbit partition for H?

P.S: I think you know what "fixing a point" means, but here is a hint. A point in a permutation set is fixed, if it is mapped to itself in all the permutations in the set. For example, 5 is mapped to 5 in g1, so 5 is fixed in g1.

2. The attempt at a solution
I want to mention two things, first the answer for the example I gave. Looking at generators g1 and g2, you realize that 3 is not fixed in any of them, but if you compose g1 and g2, you will get g1.g2=(2,5,1) which fixes 3. So you can say that the orbit of H is {{3}, {4}, {1,2,5}}.
Second, I thought that Schreier-Sims algorithm could solve this problem in general case, but then I found out that it is usually used to check membership. I have not yet found a direct link from Schreier-Sims algorithm to what I want, but there might be a way to use Schreier-Sims algorithm.

Thanks for your help! :-)

 

[metalhadi]

Hi guys,

I finally found the solution that uses the Schreier-Sims algorithm. For whom wondering the answer, take a look at section 4 of the following article:
http://bkocay.cs.umanitoba.ca/g&g/articles/isomorphismprograms.pdf

Good Luck! :-)