Let $T \subset S_n$ be a set of transpositions. Let $G = \langle T \rangle$. I want to show that $G$ has at least $n - |T|$ orbits.
Am I correct in assuming that "orbits" here is synonymous with "conjugacy classes"?
How do I go about getting started on this? I can't seem to get a foothold.
We prove this by induction. For one transposition $(ij) $, the orbits are $\{i, j\} $ and $\{k\} $ for $k\notin \{i, j\} $. Otherwise, suppose there are $m$ transpositions generating the subgroup. If we restrict to the first $m-1$, we have distinct orbits $O_p$ for $1\leq p\leq M$ with $M\geq n-m+1$.
Let the last transposition be $(ij) $. If there is a single orbit $O_p$ containing both $i$ and $j$, then the orbits of the larger subgroup are the same and the result follows. Otherwise, there is an orbit $O_p$ containing $i$ and a distinct orbit $O_q$ containing $j$. Adding $(ij) $ joins these two orbits and has no effect on the others, so there are $M-1$ orbits, and the result follows by induction.