Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
What have you tried? –  Graphth Apr 9 '11 at 13:56

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer
    
That's a good answer. Can't believe it was given as homework because it's not related to anything we learned. It's beautiful in my opinion. –  user9354 Apr 9 '11 at 14:41
    
seems like a tough homework :) (maybe there is some shortcut, but I have no idea) –  user8268 Apr 9 '11 at 14:45
    
I linked to the new version of the site. I'd be interested in hearing an easy theoretical proof (suitable for homework). I've only see the algorithm. –  Jack Schmidt Apr 9 '11 at 15:09
    
Asked the TA. Got an 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). –  user9354 Apr 9 '11 at 16:57

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.

share|improve this answer

Your Answer

 
discard

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