Timeline for the number of minimal generating subsets of a group
Current License: CC BY-SA 3.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 10, 2023 at 15:29 | comment | added | Allan Henriques | For some reason I feel like computing the number of minimal generating sets for an arbitrary group is not a computable problem in the infinite case, or atleast it would be NP complete in the finite case. | |
| Nov 10, 2023 at 9:51 | comment | added | Emil Jeřábek | Similar question: mathoverflow.net/questions/339182/… | |
| Nov 10, 2023 at 9:48 | comment | added | Emil Jeřábek | @GerhardPaseman In fact, $\sum_{i\le\log n}\binom ni\le n^{\log n}$ (with base-$2$ log) is also an upper bound, in arbitrary groups (a minimal generating subset must have size at most $\log n$). | |
| Nov 10, 2023 at 7:33 | history | edited | Martin Sleziak |
added a top-level tag; see: https://meta.mathoverflow.net/questions/1457/why-are-mo-tags-formatted-as-they-are
|
|
| Aug 23, 2016 at 5:57 | vote | accept | khers | ||
| Aug 23, 2016 at 5:57 | vote | accept | khers | ||
| Aug 23, 2016 at 5:57 | |||||
| Aug 23, 2016 at 5:53 | vote | accept | khers | ||
| Aug 23, 2016 at 5:57 | |||||
| Aug 23, 2016 at 4:36 | comment | added | Geoff Robinson | Since a minimal generating set is sent to a minimal generating set by any automorphism, in the second question, it might be better to ask for groups $G$ such that their automorphism groups transitively permute minimal generating sets. | |
| Aug 23, 2016 at 0:04 | answer | added | verret | timeline score: 4 | |
| Aug 22, 2016 at 23:43 | answer | added | Igor Rivin | timeline score: 3 | |
| Aug 22, 2016 at 21:59 | comment | added | khers | By minimal generating subsets, I mean irredundant (no proper subset of it can generate the group). Thanks | |
| Aug 22, 2016 at 21:32 | comment | added | Gerhard Paseman | With perhaps small exceptions among 2-groups, no group has a unique minimal such set, since one can substitute an element for its inverse, and for 2-groups there are certain things like conjugates that can be used for the substitution. For a finite product of copies of the two element group, there are lots of such sets, and a weak lower bound can be had by counting invertible 0-1 matrices over the two element field. The weak lower bound is like $O(n^{\log n})$, and this can doubtless be improved. Gerhard "Assuming My Memory Still Works" Paseman, 2016.08.22. | |
| Aug 22, 2016 at 21:03 | comment | added | khers | Thanks for your guidance, I will read it and it is truely very intersting. But I did not ask about the minimum number of elements in a generating subset. I try to find an upper bound on the number of generating subsets which are minimal. Not their cardinality. I need the cardinality of the collection of minimal generating subsets. Again thanks for your help. | |
| Aug 22, 2016 at 21:02 | comment | added | Francesco Polizzi | Every finite simple group can be generated by two elements, see mathoverflow.net/questions/59213/… | |
| Aug 22, 2016 at 21:00 | review | First posts | |||
| Aug 22, 2016 at 21:01 | |||||
| Aug 22, 2016 at 20:58 | history | asked | khers | CC BY-SA 3.0 |