Timeline for Cayley Graphs and Cyclically reduced words [closed]
Current License: CC BY-SA 3.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 15, 2017 at 13:01 | history | closed |
Andy Putman R.P. Yoav Kallus Stefan Kohl♦ Chris Godsil |
Not suitable for this site | |
| Jun 14, 2017 at 21:46 | comment | added | Andy Putman | @BharatRam: Ben Steinberg explained how to find a closed form solution using finite state automata. For a general finite group, you're not going to get a better answer. | |
| Jun 14, 2017 at 20:52 | history | edited | BharatRam | CC BY-SA 3.0 |
added 62 characters in body
|
| Jun 14, 2017 at 20:46 | comment | added | BharatRam | @AndyPutman Sorry, will take one of them down based on suggestions. I had posted to SE only after the comments which hinted at the questions not being too non-trivial. However, that doesn't answer the questions. Also, if the first part is trivial, I can always edit it out. The second part is still open. So why close? | |
| Jun 14, 2017 at 20:39 | review | Close votes | |||
| Jun 15, 2017 at 13:01 | |||||
| Jun 14, 2017 at 20:20 | comment | added | Andy Putman | It is not appropriate to cross-post on both math.se and MO. Also, as Derek points out your first question is trivial. I have voted to close. | |
| Jun 14, 2017 at 18:03 | history | edited | BharatRam | CC BY-SA 3.0 |
crosspost link
|
| Jun 14, 2017 at 14:19 | comment | added | BharatRam | Benjamin and Derek: Thanks. I'll look up and think to understand why/how your answers work, with the details. Is this well-studied? And could you suggest any relevant references? | |
| Jun 14, 2017 at 14:07 | comment | added | Derek Holt | If there are no involutory generators,then, as I explained in my previous comment, the answer to 1) is clearly yes. | |
| Jun 14, 2017 at 14:04 | comment | added | Benjamin Steinberg | @BharatRam, cyclically reduced should just mean that the last letter is not the inverse of the first. | |
| Jun 14, 2017 at 13:49 | comment | added | BharatRam | DerekHolt, Thanks for pointing it out. I have edited it to ensure there are no involutions in S, just to be safe. @BenjaminSteinberg Interesting direction, but is it really a regular language? Since cyclically reduced-ness depends on elements at both ends of a word not being inverses, I thought its context-free. Anyway, a bit rusty on this, and will check again. | |
| Jun 14, 2017 at 13:45 | history | edited | BharatRam | CC BY-SA 3.0 |
an extra assumption to avoid complication
|
| Jun 14, 2017 at 13:43 | comment | added | Derek Holt | For 1, since the group is finite, there is no need to use any inverses of generators, so the answer is apparently yes. But I am unclear how you are regarding involutory generators. Would you regard the word $aba$ in the group $\langle a,b \mid a^2=b^2=1, aba=bab \rangle$ as being cyclically reduced? | |
| Jun 14, 2017 at 13:37 | comment | added | Benjamin Steinberg | For 2, use that the cyclically reduced words form a regular language and the set of words representing a given element of a finite group is a regular language. Build the automaton for the intersection of these languages and use the adjacency matrix for the automaton. | |
| Jun 14, 2017 at 13:31 | history | edited | BharatRam |
edited tags
|
|
| Jun 14, 2017 at 13:24 | history | asked | BharatRam | CC BY-SA 3.0 |