6
$\begingroup$

It's well known that every subgroup $G$ of $S_n$ has a generating set of size at most $n-1$ and that this generating set can be found algorithmically (by Jerrum's filter)

I have heard many times a stronger result, which is that for all $n>3$, every subgroup $G$ of $S_n$ has a generating set of size at most $n/2$. Note that this would be tight: for example, $n/2$ disjoint transpositions cannot be minimized further.

However, as far as I can tell, none of the places I have seen this theorem give a proof, nor do their references. Can anyone point me to a proper proof, or give one, for this seemingly important theorem?

$\endgroup$
9
$\begingroup$

After some googling, one finds a few references. Most point to

Cameron, Peter J.; Solomon, Ron; Turull, Alexandre, Chains of subgroups in symmetric groups. J. Algebra 127 (1989), no. 2, 340–352.

Which itself attributes this to Peter Neumann, private communication.

They also say: "As Peter is unlikely to publish his result, we shall sketch a recipe for a proof of Neumann’s theorem here. " (And then proceed to give a sketch.)

Note that the proof seems to depend on the Classification of Finite Simple Groups (to deal with the case of primitive permutation groups).

$\endgroup$
  • $\begingroup$ Cameron has the paper available through his ResearchGate page, for anyone looking for an easily accessed copy. $\endgroup$ – zibadawa timmy Jun 10 '16 at 4:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.