Timeline for Size of a minimum generating set for full transformation monoids
Current License: CC BY-SA 4.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 1, 2018 at 17:02 | comment | added | Emil Jeřábek | ... elements ($c$, $d$, $d^{-1}$). In a similar way, we may arrange that any transposition is a product of $O(\log n)$ generators, hence any permutation a product of $O(n\log n)$ generators. It is then easy to extend this to the whole monoid. | |
| Nov 1, 2018 at 16:59 | comment | added | Emil Jeřábek | Actually, now that I think about it, there exists a constant-size set of generators (5 or so) such that every element is the product of $O(n\log n)$ generators. This implies that for any $5\le g\le n^n$, there is a set of $g$ generators such that any element is a product of $O((n\log n)/\log g)$ of them, matching the upper bound in my previous comment. The basic idea is that if $c$ is the $n$-cycle, and, say, $n$ is odd, then $c^2$ is also an $n$-cycle, thus there is a permutation $d$ such that $c^2=d^{-1}cd$. It follows easily that any power $c^j$ can be written as a product of $O(\log n)$ .. | |
| Oct 29, 2018 at 15:44 | comment | added | Emil Jeřábek | @GerhardPaseman For a lower bound, the number of compositions clearly has to be at least $(n\log n)/\log |G|$ in the worst case. For upper bounds: with the $3$-element generating set consisting of an $n$-cycle, a transposition, and a two-element collapse, $O(n^2)$ compositions suffice by mimicking insertion sort. Using bitonic mergesort or odd-even mergesort, it is easy to construct a generating set with $O(\log n)$ generators such that $O(n(\log n)^2)$ compositions suffice to generate any map. | |
| Oct 29, 2018 at 13:44 | comment | added | Benjamin Steinberg | @GerhardPaseman, I'm sure somebody has computed bounds for this generating set on lengths. My guess is they are fairly good. You need at least one rank n-1 map. I suspect the key issue is generating permutations. And this is pretty efficient even though the inverse is not part of the signature. Then you can get all rank n-1 maps as fgh where f,h are permutations and f is your favorite rank n-1 map. To get a general map of rank r <n-1you can write it as a single rank n-1 map composed with a rank r+1 map. So it seems to me this is basically (n-2)+1+f(n)^2 where f(n) is the worse perm length | |
| Oct 24, 2018 at 14:53 | comment | added | Gerhard Paseman | With a small generating set, it may take a large number L(pi) of compositions of generators for a given map pi. Is there a slightly larger set G of generators which can sharply decrease the maximum such L needed? As a first take, minimize |G|(Max L(pi)). Gerhard "Wants To Get There Faster" Paseman, 2018.10.24. | |
| Oct 24, 2018 at 14:13 | history | edited | Benjamin Steinberg | CC BY-SA 4.0 |
added 139 characters in body
|
| Oct 24, 2018 at 13:53 | vote | accept | Ethan Splaver | ||
| Oct 24, 2018 at 13:52 | comment | added | Benjamin Steinberg | It is easy once you know the trick. But people don’t learn it in a basic algebra course like generating the symmetric group by transpositions, | |
| Oct 24, 2018 at 13:50 | comment | added | Ethan Splaver | I think I get it. Is this result rather trivial then? Sorry I don't have any experience with this sorta stuff. | |
| Oct 24, 2018 at 13:50 | history | edited | Benjamin Steinberg | CC BY-SA 4.0 |
added 1 character in body
|
| Oct 24, 2018 at 13:48 | comment | added | Benjamin Steinberg | To get 3 I can't use all transpositiins. The point is the monoid is generated by the symmetric group and any map collapsing exactly two elements and you can fix your favorite symmetric group generating set. | |
| Oct 24, 2018 at 13:47 | comment | added | Ethan Splaver | Why is the $n$-cycle needed? It seems all you need is functions which move just one element, and then transpositions | |
| Oct 24, 2018 at 13:45 | comment | added | Benjamin Steinberg | It takes 3 maps all togethe to generate the full monoid. An n-cycle, a transposition and the map sending n to n-1 and fixing all other elements. I provided some hints. | |
| Oct 24, 2018 at 13:43 | history | edited | Benjamin Steinberg | CC BY-SA 4.0 |
added 310 characters in body
|
| Oct 24, 2018 at 13:40 | comment | added | Benjamin Steinberg | This can be found in virtually any book on finite semigroup including my book with John Rhodes the q-theory of finite semigroups. | |
| Oct 24, 2018 at 13:39 | history | answered | Benjamin Steinberg | CC BY-SA 4.0 |