Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $S_n$ be the set of all permutations that act on $1...n$. You are given a subset $P\subseteq S_n$, and you are to compute the size of the set $G(P) \subseteq S_n$, where $G(P)$ meets the following requirements:

  1. $G(P)$ contains the identity permutation,
  2. $P \subseteq G(P)$,
  3. $G(P)$ is closed under taking inverses and multiplications (if $a, b \in G(P)$, then $ab \in G(P)$, if $a \in G(P)$, then $a^{-1} \in G(P)$),
  4. $G(P)$ is a minimal possible set that meets requirements 1,2 and 3.

Is there a method or algorithm that can solve this?

share|improve this question
9  
So in other words $G(P)$ is the subgroup of $S_n$ generated by $P$. The principal algorithm for this (which is polynomial-time) is known as the Schreier-Sims algorithm. –  Derek Holt Apr 27 '12 at 8:30
1  
Thank you for your help :) –  Lwins.Gafield Apr 27 '12 at 11:47
    
@Derek: poly time in what? The size of output? –  Igor Rivin Apr 27 '12 at 15:42
1  
@Igor: Size of input. Lwins.Gafield just asked for the order of the group, but the output is actually a data structure, known as a base and strong generating set, that tells you the order, and also allows you to test quickly whether a given permutation in $S_n$ is in $G(P)$ and, if so, to express it as a word (more precisely a Straight Line Program) in $P$. Almost all other algorithms for computing structural information about $G(P)$ make use of this data structure. –  Derek Holt Apr 27 '12 at 21:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.