Timeline for Generating n-cycles
Current License: CC BY-SA 2.5
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 14, 2010 at 10:50 | comment | added | Gordon Royle | The argument that "you can take commutators of pairs of words whose support intersects only modestly ... " is the heart of the proof by Babai, Beals and Seress (paper referred to above by Zaimi) that if there is any element in the generating set with support of size less than n/3 then the diameter of the Cayley graph is polynomially bounded. So, as you say, it seems difficult to imagine how there could be counterexamples, but I can't see any strategy to prove it. | |
| Sep 12, 2010 at 14:51 | comment | added | Jack Schmidt | "Words in words in ..." are called "straight line programs" to the algorithmic folks, and yes they are used quite a bit. Actual words take a long time to multiply (in the free group, on a computer), just because word lengths get large (exponentially large when using the standard computational algorithms for permutation groups). However, to multiply the 3rd word by the 4th word, you just write down [3,4] in a straight line program, eliminating concerns about word length. Unfortunately, this also means many algorithms used in practice produce exponentially long words. | |
| Sep 12, 2010 at 1:14 | history | edited | Bill Thurston | CC BY-SA 2.5 |
formatting, grammar and clarity corrections
|
| Sep 12, 2010 at 0:24 | history | answered | Bill Thurston | CC BY-SA 2.5 |