# Is $S_n$ generated by a maximum of n-2 transpositions?

Let $S_n$ be the group of all permutations of the set {$1, 2, \dots,n$}.

The question is whether $S_n$ is generated by a maximum of $n-2$ of its transpositions or not.

Definitions: A permutation of a set $X$, which is a bijective function $\sigma :X\to X$, is called a cycle if the action on $X$ of the subgroup generated by $\sigma$ has exactly one orbit with more than a single element.

A cycle with only two elements is called a transposition.

-

If $\mathcal T$ is a set of transpositions, let $\Gamma(\mathcal T)$ be the graph with vertices $1$, $\dots$, $n$ and in which two vertices $i$ and $j$ are connected by an edge iff $(ij)\in\mathcal T$.

Then $\mathcal T$ generates $S_n$ iff $\Gamma(\mathcal T)$ is connected.

Now, since $\Gamma(\mathcal T)$ has $n$ vertices, one needs at least $n-1$ edges if it is to be connected, so one needs at least $n-1$ transpositions to generate $S_n$.

-
Is there some elementary proof that $\Gamma(\mathcal T)$ is connected implies $\mathcal T$ generates $S_n$? –  user641 Dec 21 '11 at 6:27
@SteveD: Yes. Induction on $n$ with $n\leq1$ trivial. First reduce to the case $\Gamma(T)$ is a spanning tree by dropping superfluous edges. Finite trees of size $n>1$ have (at least $2$) leaves, choose one $x$ with remaining tree $R$. If $x$ is a fixed point of the sought permutation apply induction to $R$. If not, permute $R$ (again induction) so that the element that should map to $x$ becomes its neighbour, interchange it with $x$, and finish by another permutation of $R$ supplied by the induction hypothesis. –  Marc van Leeuwen Dec 21 '11 at 14:11
@MarcvanLeeuwen: Thank you! –  user641 Dec 21 '11 at 16:06

Assume it is true that $S_n$ is generated by a maximum of $n-2$ transpositions. Then $S_3$ would be generated by $1$ transposition. But this is impossible because any transposition has order $2$ and so the cyclic group it generates has only two elements. But $S_3$ has $6$ elements.

Try proving that $S_n$ is generated by exactly $n-1$ transpositions. Use induction. For $S_2$ it is obvious. Then show that $S_n$ can be obtained from $S_{n-1}$ by introducing a transposition that contains the symbol $n$.

-
Your first paragraph leaves the possibility that $S_n$ is generated by $n-2$ transpositions for all $n>3$ :) –  Mariano Suárez-Alvarez Dec 21 '11 at 14:47
True. I am just refuting the general statement made by the author of the question. –  Manos Dec 21 '11 at 19:40