I'm looking for an easy characterization of transpositions $\pi_1, \ldots, \pi_d \in S_d$ that generate $S_d$ or a transitive subgroup thereof (this should be equivalent).
Examples include
- $(1 2), (1,3), \ldots, (1 d)$ or
- $(1 2), (2, 3) \ldots, (d-1 d)$
- all transpositions
I can't help thinking of the problem but in terms of graph theory. Take a graph $G$ with vertices $\{1, \ldots, d\}$ and add an edge $\{i,j\}$ iff there is some transposition $\pi_i = (i j)$.
Is my following idea correct?
- For the $\pi_i$'s to generate full $S_d$, we need $G$ to be connected because orbits of vertices stay in a connected component.
- If $G$ is connected, the $\pi_i$'s generate $S_d$ because we get all transpositions by conjugating along suitable paths
Thereby, sets of transpositions generating the symmetric group correspond to connected graphs on $d$ vertices? Minimal sets of transpositions correspond to $n$-trees?
Am I missing something; do you know any work studying transpositions and graphs in this way? And is there a common characterizations without graph theory? Thanks
You right in both cases. If you view a transposition as an edge in $K_n$, then a set of transpositions generates the symmetric group if the corresponding graph is connected, and sow mminimal generating sets correspond to trees on $n$ vertices.
This result is folklore. There is a discussion of it in Section 3.10 of "Algebraic Graph Theory" by Royle et al.