# Transitive subgroup of symmetric group

I'm working on the following question, and honestly have no idea how to begin. Any hints would be greatly appreciated!

Let $H$ be a subgroup of $S_n$, the symmetry group of the set $\{1,2,\dots, n\}$. Show that if $H$ is transitive and if $H$ is generated by some set of transpositions, then $H=S_n$.

This might not be at the appropriate level for you, but I think this is a cute argument.

Suppose we wanted to transpose $1$ and $n$ in the list $1,\cdots,n$ but we were only allowed to swap adjacent numbers each step, how would we do it? Well, we could use adjacent transpositions to move $1$ all the way to the right, which would shift the numbers $2,\cdots,n$ each one left. Then we could move $n$ to the left with adjacent transpositions until we get the list $n,2,\cdots,n-1,1$.

In other words, we have

$$(12)(23)\cdots(n-2\,n-1)\cdot(n\,n-1)\cdots(32)(21)=(n1). \tag{\ast}$$

(Remember, the rightmost permutations are applied to an input first. Interpret $(u\,v)$ as "swap the numbers that are $u$th and $v$th in the list.") We can use this...

Form a graph as follows: given a generating set $S$ of $H$ consisting of transpositions, let $\{1,\cdots,n\}$ be the vertex set and form an edge $(i,j)$ for every transposition $(ij)\in S$. The hypotheses that $H$ acts transitively and is generated by $S$ is equivalent to saying this graph is connected, so between any two values $a,b\in\{1,\cdots,n\}$ there is some sequence of transpositions

$$(a_1\,a_2),(a_2\,a_3),\cdots,(a_{k-1}\,a_k)\in S$$

where $a_1=a$ and $a_k=b$. Then we can reuse the $(\ast)$ trick:

$$(a_1\,a_2)(a_2\,a_3)\cdots(a_{k-2}\,a_{k-1})\cdot(a_k\,a_{k-1})\cdots(a_3\,a_2)(a_2\,a_1)=(a_k\,a_1)=(ab)\in H.$$

That is, $H$ contains every transposition $(ab)$, so it must be $S_n$.

• I honestly don't follow. – mathgenesis22813 Nov 1 '16 at 2:27
• @m2271r As I stated at the very beginning of my answer, I wasn't sure if this was written well for you specifically (it uses graph theory for instance). But if you're interested in engaging the argument, "I don't follow" is pretty much a useless comment since you don't specify any of the many things I said that you don't follow. If you're interested in engaging the argument, you might as well start by saying what is the very first part that you don't follow. Perhaps I can rephrase the argument later too. – arctic tern Nov 1 '16 at 2:39

Proof by induction on $$n$$. Case $$n\le 2$$ is trivial.

Let $$X$$ be the set of transpositions in $$H$$, $$X_1$$ the set of transpositions in $$X$$ fixing 1 and $$K$$ the subgroup generated by $$X_1$$.

We have to prove that $$K$$ is transitive on $$\{2,\dots,n\}$$. If true, induction hypothesis implies $$K$$ is the full symmetry group on $$\{2,\dots,n\}$$, and since $$H$$ properly contains $$K$$ which is a maximal subgroup in $$S_n$$, it's immediate to conclude.

So let's prove this transitivity claim on $$K$$. Otherwise $$K$$ has at least two orbits $$I,J$$ in $$\{2,\dots,n\}$$. Since $$H$$ does not stabilize $$I$$ and is generated by transpositions, it contains a transposition $$t=(u,v)$$ with $$u\notin I$$ and $$v\in I$$. If $$u\neq 1$$, we deduce that $$t\in X_1\subset K$$ and deduce that $$u$$ is in the same $$K$$-orbit as $$v$$, a contradiction. So $$u=1$$ and $$H$$ contains the transposition $$(1,v)$$, $$v\in I$$. Similarly, $$H$$ contains a transposition $$(1,w)$$ with $$w\in J$$. Hence $$H$$ contains $$(1,v)(1,w)(1,v)=(v,w)$$. This is again a contradiction since this transposition would have to belong to $$K$$ and contradict that $$v,w$$ are in distinct $$K$$-orbits. So $$K$$ is transitive on $$\{2,\dots,n\}$$. This finishes the proof.

• If K is transitive on {2,â€¦,n}, wouldn't induction hypothesis implies K is the full symmetry group on {2,â€¦,n}? – Samantha Wyler Jun 3 '20 at 22:21
• @SamanthaWyler yes! $n-1$ was a typo, I fixed it. – YCor Jun 3 '20 at 22:49

So I am convinced that I am miss understanding the question and its probably due to the fact that I am miss understanding the definition of $$H$$ being a transitive subgroup of $$S_n$$

Since $$H$$ is a transitive subgroup of $$S_n$$ I believe that means for any $$\sigma, \tau \in S_n$$ there exists an $$h \in H$$ such that $$\sigma h = \tau$$.

If this definition is correct then we can consider an arbitrary $$\sigma \in S_n$$. Let $$h_1 \in H$$ since $$H$$ is a subgroup of $$S_n$$ we have $$h_1 \in S_n$$ and so since $$H$$ is a transitive subgroup of $$S_n$$ we get that there is an $$h_2 \in H$$ such that $$h_2h_1 = \sigma$$ but since $$H$$ is a group and hence closed under multiplication we have $$\sigma = h_2h_1 \in H$$ and since $$\sigma \in S_n$$ was arbitrary $$S_n = H$$

I am definitly not understanding something about this question because otherwise this problem was to easy and the fact that $$H$$ is generated by some set of transpositions was completely irrelevant information.