Permutation groups generated by transpositions

Question

A transposition is a permutation of the form $\tau = (i\thinspace j) \in S_n$.

Let $\{ \tau_1, \dots, \tau_k \}$ be a set of distinct transpositions of $S_n$.

Will this set necessarily generate a group isomorphic to $S_k$?

Answer 1

Consider $(12)$ and $(34)$ in $S_4$. They two together generate a group isomorphic to the Klein $4$-group which is not isomorphic to $S_n$ for any $n$.

Answer 2

No, in general you need special transpositions to work. For example, the $k-1$ tranpositions $$ (12),(13),\ldots ,(1k) $$ generate $S_k$, as do the $k-1$ transpositions $$ (12),(23),\ldots ,(k-1,k). $$

Answer 3

There are k(k-1)/2 transpositions in S_k, and therefore (k-1)(k-2)/2 transpositions in S_k-1. So it's possible to choose k transpositions from S_k-1. Since those transpositions are restricted to k-1 elements, there's no way they can generate a group on k elements (if k>3).

If all of this is too abstract, consider the digits (so n = 10). If we take a subset of five digits, there will be 10 transpositions of those digits:

01 02 03 04 12 13 14 23 24 34

It should be quite obvious that if we take k of these transpositions, they will generate a (possibly improper) subgroup of S₅. So if k is, say, 6, then we have 6 transpositions that all lie in S₅. There are only 5 elements that these 6 transpositions act on, so there's no way they can generate something isomorphic to S₆.

It's possible to generate S_k with only k-1 transpositions. I believe that a necessary and sufficient condition for k-1 transpositions to generate S_k is that the transpositions be such that they can be ordered in such a way that each transposition other than the first one involves an element involved in a previous transposition and an element not involved in a previous transposition. For instance, for k = 6:

(01) first transposition can be anything we want

(12) 1 was used in a previous transposition, 2 was not

(23) 2 was previously used, 3 was not

(04) 0 was previously used, 4 was not

(15) 1 was previously used, 5 was not

Thus the transpositions (01),(12),(23),(04),(15) generate all permutations of {0,1,2,3,4,5}.