Subgroup rank of symmetric group is about half the degree
- If is even, the subgroup rank of is .
- If , the subgroup rank of is .
- If is any odd positive integer other than 3, the subgroup rank of is .
The subgroup rank is defined as the maximum, over all subgroups, of the minimum size of generating set of that subgroup. In particular, this means that every subgroup of has a generating set of size at most the subgroup rank, and there is at least one subgroup of for which the minimum size of generating set equals the subgroup rank.
|(order of symmetric group)||symmetric group of degree||subgroup rank|
- Jerrum's filter gives an algorithmic method for finding a Jerrum-reduced generating set for any subgroup, and such a generating set must have size at most .
- Sims filter gives an algorithmic method for finding a Sims-reduced generating set for any subgroup, and such a generating set must have size at most .
The easy part: finding subgroups where the maximum is attained
For simplicity, we take the symmetric group on the set .
Case of even : In this case, consider the subgroup:
Case of : In this case, the whole group has minimum size of generating set equal to 2.
Case of odd (): In this case, consider the subgroup: