> < ^ Date: Mon, 30 Sep 2002 10:50:52 +0100
> ^ From: Christopher Jefferson <caj@cs.york.ac.uk >
> ^ Subject: Complexity of group problem

Hello,

I apologize in advance if I am asking a simple question I should be able to
find the answer to, but I have been unable to do so.

I am dealing with a problem where I have a permutation group G defined over
the integers 1...n, generated by a set of generators S

I want to find orbit(1), orbit(2) in "stabilizer of 1", orbit(3) in
"stabilizer of 1 and stabilizer of 2", etc.

Given the generators of a group as defined above I can find the orbit of an
element in about O(|S|n+n^3), possibly more efficently than that, so what I
need to work out is the generators of the stabilizing groups. I believe
this is called a "stabilizer chain" in GAP.

What I am having problems finding is the complexity of calculating these
new generator sets, and what the limit (hopefully there is one) on the size
of the sets.. could anyone help me find the complexity of this operation,
and the size of the resulting generator sets? Perferably in terms of |S|
and n if possible.

Thank you,

Chris


> < [top]