"Natural" generating sets for symmetric groups. - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T09:39:52Z http://mathoverflow.net/feeds/question/24101 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/24101/natural-generating-sets-for-symmetric-groups "Natural" generating sets for symmetric groups. Roland Bacher 2010-05-10T13:52:52Z 2010-05-10T20:59:45Z <p>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).</p> <p>Which other sets of generators of symmetric groups occur in a natural way?</p> http://mathoverflow.net/questions/24101/natural-generating-sets-for-symmetric-groups/24115#24115 Answer by André Henriques for "Natural" generating sets for symmetric groups. André Henriques 2010-05-10T15:07:46Z 2010-05-10T15:07:46Z <p>Here's an example: One transposition, and one cycle of length n.</p> http://mathoverflow.net/questions/24101/natural-generating-sets-for-symmetric-groups/24128#24128 Answer by Igor Pak for "Natural" generating sets for symmetric groups. Igor Pak 2010-05-10T18:28:45Z 2010-05-10T18:28:45Z <p>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:</p> <p>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 <a href="http://dx.doi.org/10.1016/j.disc.2009.02.018" rel="nofollow">here</a> for many refs to $(2,2\times 2)$ generating sets. </p> <p>2) $s_i = (1,i)$, $i=2\ldots n$. These are called "star transpositions" and have a number of interesting combinatorial properties. See <a href="http://tinyurl.com/yfo57t4" rel="nofollow">here</a> (pref-f. 2b) how they come up in Knuth ACP. </p> http://mathoverflow.net/questions/24101/natural-generating-sets-for-symmetric-groups/24156#24156 Answer by KConrad for "Natural" generating sets for symmetric groups. KConrad 2010-05-10T20:59:45Z 2010-05-10T20:59:45Z <p>I wrote a handout on generating sets for symmetric and alternating groups for an algebra course. It's available at <a href="http://www.math.uconn.edu/~kconrad/blurbs/grouptheory/genset.pdf" rel="nofollow">http://www.math.uconn.edu/~kconrad/blurbs/grouptheory/genset.pdf</a>. The table at the end of Section 1 lists several choices of generating sets for $S_n$ and $A_n$.</p>