Permutation groups generated by transpositions

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

• Think as the transpositions as labelling some edges in a complete graph. They correspond to a subgraph of the complete graph. If this subgraph is connected, then the group is an $S_k$, and conversely. Mar 8 '18 at 12:35
• Ok, so you are saying that the subgroups generated by transpositions are in fact direct products of (smaller) symmetric groups? Mar 8 '18 at 12:37
• Yes, they are such products. Mar 8 '18 at 12:38

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

• Excellent, thank you! Mar 8 '18 at 12:22
• You are welcome. Mar 8 '18 at 12:22

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).$$

• I see, thanks. Perhaps a separate question, but can any subgroup of $S_n$ be generated by a set of transpositions? Mar 8 '18 at 12:29
• No, if a subgroup is generated by transpositions, then it must have even order. But for example $S_3$ has a subgroup of order $3$. Mar 8 '18 at 12:29
• What about $(12),(13),(34)$ in $S_4$? They generate $S_4$, right? Mar 8 '18 at 12:31
• @ user353673 All subgroups generated by transpositions are isomorphic to a product of symmetric groups. So your question boils to whether there are subgroups that aren't isomorphic to a product of symmetric groups. And the answer is "yes". For instance, the kth cyclic group is a subgroup for k<=n, and if k > 2, this in not isomorphic to a product of symmetric groups. Mar 8 '18 at 16:44
• @Levent Yes, those aren't the only types of generating sets. But your set is actually equivalent to the second type of generating set that Dietrich Burde presented. Suppose I take your proposed transpositions and swap out 1 for 2, and vice versa. That is, I'm going to rewrite your transpositions, putting a 1 wherever I see a 2 in your transpositions, and a 2 wherever I see a 1. This results in (21), (23), (34), which is the same as (12), (23), (34). Since the labels are arbitrary, relabeling shouldn't change whether they generate the group. Mar 8 '18 at 16:51

There are k(k-1)/2 transpositions in Sk, and therefore (k-1)(k-2)/2 transpositions in Sk-1. So it's possible to choose k transpositions from Sk-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 S5. So if k is, say, 6, then we have 6 transpositions that all lie in S5. There are only 5 elements that these 6 transpositions act on, so there's no way they can generate something isomorphic to S6.

It's possible to generate Sk with only k-1 transpositions. I believe that a necessary and sufficient condition for k-1 transpositions to generate Sk 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}.

• Another necessary and sufficient condition for the set of transpositions to generate $S_n$ is that for any partition of the set of objects being transposed into two non-empty sets $A$ and $B$, there must be at least one transposition in the set that exchanges a member of $A$ with a member of $B$. Mar 8 '18 at 18:23