Timeline for Determining whether or not a subset of $S_n$ generates $S_n$
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 9, 2016 at 13:51 | comment | added | David E Speyer | To build on Derek Holt's comment, Bratus and Pak math.ucla.edu/~pak/papers/recfin.pdf give such an algorithm. | |
| Jun 8, 2016 at 17:40 | comment | added | Jack M | @DerekHolt Theoretical results. | |
| Jun 8, 2016 at 17:20 | comment | added | Derek Holt | For general algorithms for computing $|\langle S \rangle|$ you could start by searching for "Schreier-Sims algorithm". | |
| Jun 8, 2016 at 17:12 | comment | added | Derek Holt | Are you looking for theoretical results, or for an algorithm? There is a fast Monte-Carlo algorithm for verifying that $\langle S \rangle = S_n$. | |
| Jun 8, 2016 at 17:10 | answer | added | Jan-Christoph Schlage-Puchta | timeline score: 4 | |
| Jun 8, 2016 at 15:13 | answer | added | Peter Mueller | timeline score: 8 | |
| Jun 8, 2016 at 14:43 | comment | added | Denis Chaperon de Lauzières | Without knowing more, what comes to mind is to look at the classification of maximal subgroups of $S_n$; if your subset does not generate $S_n$, it must be contained in one of these. The following paper (Liebeck, Praeger, Saxl) seems to have such a classification sciencedirect.com/science/article/pii/0021869387902237 building on the O'Nan--Scott Theorem. | |
| Jun 8, 2016 at 14:02 | comment | added | Jack M | I hope this question isn't too broad, but I'm not sure how to narrow it down. | |
| Jun 8, 2016 at 14:01 | history | asked | Jack M | CC BY-SA 3.0 |