Say that $a_1, \cdots, a_{n-1}$ is an independent generating set for $S_n$. Let $b$ be any element in $S_n$. Is it true that $b$ can replace one of the generators, i.e. that there exists an index $i$, such that we have that $a_1,\cdots, \hat{a_i},\cdots, a_{n-1}, b$ generate $S_n$?
If $a_1, \cdots, a_{n-1}$ is the standard (n-1)-tuple that generates $S_n$, $(12),(13),…,(1n)$, then it's true and it can easily be shown. Does it hold in general?
Best Answer
The answer is yes.
There is a paper by Cameron and Cara which describes all maximal generating sets of length $n-1$ of $S_n$. They are not very hard to describe and basically are variants of the standard $n-1$ length generating sets.
http://www.maths.qmul.ac.uk/~pjc/preprints/igsgsn.pdf
Cameron and Cara say build a tree with the vertices being $\{1,\ldots,n\}$. Add transpositions corresponding to edges into your generating set. These are (about) half the maximal length generating sets. The other set is found by taking one of those generating sets, picking a transposition and multiplying against all the others.
In both cases it is pretty clear that given a $b$ we can find an edge to replace. Basically $b$ will connect some vertices of the tree, and we can remove an edge to have the tree be connected, and since everything is basically a transposition this is all you really need. I can supply more details if this was unclear, but I think just given the Cameron paper things become clear.