"Natural" generating sets for symmetric groups. - MathOverflow

"Natural" generating sets for symmetric groups.

2010-05-10T13:52:52Z

The symmetric group on $n$ letters has many sets of generators. Some of them are more natural than others, eg the set $(i,i+1)$ of adjacent transpositions (natural with respect to the type A Weyl group), the set of all shuffles (permutations corresponding to "card-shuffles", ie $\sigma(1),\sigma(2),\dots,$ contains at most two increasing subsequences) perhaps also sets consisting of conjugacy classes (preferably of signature $-1$ in order to avoid a stupid mistake).

Which other sets of generators of symmetric groups occur in a natural way?

Answer by André Henriques for "Natural" generating sets for symmetric groups.

2010-05-10T15:07:46Z

Here's an example: One transposition, and one cycle of length n.

Answer by Igor Pak for "Natural" generating sets for symmetric groups.

2010-05-10T18:28:45Z

I am not exactly sure what you looking for. As you know, two random permutations generate $S_n$ or $A_n$ with probability $\to 1$ as $n\to \infty$. However, if you are looking for generating sets that came up in my work, here a a couple:

1) $a = (12)(34)\cdots$, $b= (23)(45)\cdots$, $c=(12)$. The generating set ${a,b,c}$ comes up in a number of problems and even has a name $(2,2\times 2)$ generating set (three involutions two of which commute). See here for many refs to $(2,2\times 2)$ generating sets.

2) $s_i = (1,i)$, $i=2\ldots n$. These are called "star transpositions" and have a number of interesting combinatorial properties. See here (pref-f. 2b) how they come up in Knuth ACP.

Answer by KConrad for "Natural" generating sets for symmetric groups.

2010-05-10T20:59:45Z

I wrote a handout on generating sets for symmetric and alternating groups for an algebra course. It's available at http://www.math.uconn.edu/~kconrad/blurbs/grouptheory/genset.pdf. The table at the end of Section 1 lists several choices of generating sets for $S_n$ and $A_n$.