Consider all minimal generating sets for $S_n$. The smallest of them have size 2, that is, $S_n$ can be generated by two permutations. What are the largest ones?
As I understand, there should exist minimal generating sets of size $n – 1$. E.g. the Coxeter generating set $(1\;2),\, (2\;3),\, \dots,\, (n – 1\;n)$ appears to be minimal: if we remove any single permutation $(i\;i + 1)$, then $S_i \times S_{n-i}$ will be generated. And also $(1\;2),\, (1\;3),\, \dots,\, (1\;n)$ appears to be minimal: without any single permutation, $S_{n-1}$ will be generated.
Is it true that a minimal generating set for $S_n$ cannot have more than $n – 1$ elements? Is it somehow related to Jerrum's filter that is guaranteed to return a generating set of size $\le n – 1$?
Best Answer
The maximal size of an irredundant generating set of $S_n$ is proved to be $n-1$ in the paper
Julius Whiston, Maximal Independent Generating Sets of the Symmetric Group, Journal of Algebra 232, 255-268 (2000).
You can find this online by searching for it.