7
$\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$

1 Answer 1

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$
1
  • $\begingroup$ Cameron has the paper available through his ResearchGate page, for anyone looking for an easily accessed copy. $\endgroup$ Commented Jun 10, 2016 at 4:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .