3
$\begingroup$

Given a subgroup G of $S_n$. I want to prove that G can be generated by (at most) n-1 elements.

All my ideas so far seem irrelevant. A hint would be greatly appreciated.

My attempts so far: n-1 reminds me of the number of transpositions required to generate $S_n$, so I'm trying to generalize that, but with no success.

2 Answers 2

2

Jerrum's filter provides such a generating set. (it's a homework, so perhaps a link is not a completely bad answer)

  • 0
    Asked the TA. Got a$n$ apology followed by an email to all students saying this Q in canceled. So unfortunately I can't provide an easy proof. Thank you very much for the help (I enjoyed the solution).2011-04-09
6

You might be interested to know that Peter M. Neumann proved that, with the exception of the symmetric group of degree 3 (which requires 2 generators), every subgroup of $S_n$ can be generated by at most $n/2$ elements. This result is sharp, because (for $n$ even), the group generated by the $n/2$ transpositions $(1,2), (3,4), \ldots, (n-1,n)$ cannot be generated by fewer elements.

I don't think Neumann ever published his proof, but there is a sketch of it in Section 4 of the paper ``Chains of subgroups in symmetric groups" by P. Cameron, R. Solomon and A. Turull, J. Algebra 127, 340-352, 1989.