0
$\begingroup$

Given a Symmetric group $S_n$, I need to find the smallest generating set for $S_n$. I know it is given by $\langle S_n\rangle$, where

$$\langle S_n \rangle = \{(12),(13), \cdots,(1 n)\}$$ There are $n$ many transpositions in the generating set $\langle S_n \rangle $.

I know there are many generating sets for $S_n$, but I am only interested in those that contains only transpositions. For example $S_n = \langle(1 2),(12\cdots n)\rangle$ is also a generating set for $S_n$ but it is not valid according to my problem.

My Question : How to prove that generating set for $S_n$ contain at least $n - 1$ transpositions ?

$\endgroup$
  • 2
    $\begingroup$ $S_n=\langle(1\,2),(1\,2\,3\,\ldots\,n)\rangle$, so one transposition (and a cyclic premutaion) suffice ... $\endgroup$ – Hagen von Eitzen Jul 3 '17 at 6:27
  • $\begingroup$ @HagenvonEitzen I believe OP is looking for a generating set of transpositions, but the question is definitely unclear. $\endgroup$ – diracdeltafunk Jul 3 '17 at 7:07
  • 1
    $\begingroup$ @Hagen von Eitzen and diracdeltafunk In the question I have mentioned that transposition not cycle $\endgroup$ – user275490 Jul 3 '17 at 7:11
  • $\begingroup$ @ diracdeltafunk What is thing that is unclear to you ? $\endgroup$ – user275490 Jul 3 '17 at 7:12
  • $\begingroup$ Please separate items in a list with commas. Otherwise people are entitled to read them as products. So, for example, $(12)(13)$ is not a list of two transposition, but rather their product $=(132)$. $\endgroup$ – Jyrki Lahtonen Jul 3 '17 at 7:53
9
$\begingroup$

Think of transpositions as edges in a graph with vertex set $\{1,2,\ldots,n\}$. For the transpositions to generate $S_n$, this graph must be connected.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy