12
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • 3
    $\begingroup$ I presume you mean an irredundant generating set of size $n-1$ ( ie $n-1$ elements such that no proper subset generates, but the whole set does). If you don't insist on size $n-1$, then there are examples: eg $S_{7} = \langle (12),(1234567) \rangle$, but $S_{7}$ is not generated by $(12)$ and any $5$-cycle. I am not sure how many irredundant generating sets for $S_{n}$ have size exactly $n-1$ -maybe relatively few. $\endgroup$ – Geoff Robinson Mar 19 '15 at 19:18
  • $\begingroup$ Yes, I mean that no proper subset generates it. It must be of cardinality $n-1$. There are surprisingly a lot of such sets generating $S_n$! $\endgroup$ – Nela Mar 19 '15 at 19:29
10
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Thanks for indicating this paper. As I can see the independent generating sets of size $n-1$ have the following form: either they are all transpositions, or there is one transposition and the rest of them are 3-cycles or double transpositions. What if $b$ is a 5-cycle? how can it replace one of the generators? sorry, maybe I am missing something $\endgroup$ – Nela Mar 20 '15 at 6:47
  • $\begingroup$ I suppose it could be that when $b$ replaces a generator, you get a generating set, but it will no longer be independent when $b$ is not a transposition, $3$-cycle, or double transposition. $\endgroup$ – Geoff Robinson Mar 20 '15 at 10:04
  • $\begingroup$ As Geoff Robinson if $b$ is a $5$-cycle, there is no hope to get an independent generating set, but you get a generating set nonetheless. Basically you can think of $b$ as adding more edges on the tree. If you add those edges there should be an original edge you can remove to keep the graph connected. Note it is possible never to remove the tranposition in the case when the sequence only has one because $b$ will connected more than just the two vertices involved. Then to check if the set generates you can assume everything you are left with is a transposition $\endgroup$ – user45150 Mar 20 '15 at 14:56
  • $\begingroup$ Basically you have a tree with an edge removed. To get an arbitrary permutation use the original transpositions to get the permutation as you like it on either connected component, and use $b$ to move between the connected components $\endgroup$ – user45150 Mar 20 '15 at 14:57
6
$\begingroup$

Note (too long for a comment). The maximal non-redundant generating set of $S_n$ has size $n-1$. This is a difficult theorem by J. Whiston. The proof depends on CFSG.

Julius Whiston, Maximal Independent Generating Sets of the Symmetric Group, Journal of Algebra, Vol. 232 (2000), 255–268.

UPDATE: Right, this does not answer the question. Please accept user45150's answer.

|cite|improve this answer
$\endgroup$
  • 7
    $\begingroup$ This does not answer the question. $\endgroup$ – Andreas Thom Mar 19 '15 at 22:02
  • 2
    $\begingroup$ It is unclear to me why ( for an arbitrary irredundant such set of generators), we can't have some non-identity element $b \in \cap_{k=1}^{n-1} H_{k}$, where $H_{i} = \langle a_{j}: j \neq i \rangle$ for $1 \leq i \leq n-1$, even given Whiston's theorem. $\endgroup$ – Geoff Robinson Mar 19 '15 at 23:39

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.