Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

It is easy to check by hand that (12) generates S_2, (12) and (123) generate S_3, (12) and (1234) generate S_4 and so on.... Are there other generating pairs? If so how many and is there a method or algorithm to find them all? What about generating n-tuplets in general? Characterizing generating sets of S_n in full generality is, to my knowledge, still an open problem. However a lot of asymptotic/probabilistic answers are known. For example Netto conjectured that as n tends to infinity, almost all pairs in S_n will generate either S_n, or A_n; more precisely, if we pick two permutations at random, then the probability theat they generate either S_n, or A_n tends to one as n tends to infinity. Since 3/4 of all pairs in S_n contain at least one odd permutation, it follows that the probability that a chosen pair generates S_n tends to 3/4 as n tends to infinity. J. D. Dixon gave a beautifully simple proof of this result in 1968. I will follow Dixon's argument in as much detail as time permits.