Word length perturbations in certain symmetric presentations of dihedral groups. (English) Zbl 1403.20034
The authors classify all small symmetric presentations of the dihedral group \(D_n\) (here, “small” means a generating set with at most three elements and “symmetric” means that the generating set \(S\) contains only nontrivial elements and if \(s\in S\), then \(s^{-1}\in S\)).
The length of an element \(g\in D_n\) with respect to such a symmetric generating set \(S\) is simply the minimal number of letters in \(S\) needed to write the word \(g\). Two special integers are defined to measure somehow the effect on the length of the deletion of a letter or the replacement of a letter with another. Exact values for these two special integers are obtained for various symmetric generating sets and general bounds for other symmetric generating sets.
The length of an element \(g\in D_n\) with respect to such a symmetric generating set \(S\) is simply the minimal number of letters in \(S\) needed to write the word \(g\). Two special integers are defined to measure somehow the effect on the length of the deletion of a letter or the replacement of a letter with another. Exact values for these two special integers are obtained for various symmetric generating sets and general bounds for other symmetric generating sets.
Reviewer: Marian Deaconescu (Safat)
MSC:
| 20D60 | Arithmetic and combinatorial problems involving abstract finite groups |
| 20F10 | Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) |
| 20F05 | Generators, relations, and presentations of groups |
Software:
Group ExplorerReferences:
| [1] | Bafna, V.; Pevzner, P. A., Genome rearrangements and sorting by reversals, SIAM J. Comput., 25, 2, 272-289 (1996) · Zbl 0844.68123 |
| [2] | Bergeron, A., A very elementary presentation of the Hannenhalli-Pevzner theory, Discrete Appl. Math., 146, 2, 134-145 (2005) · Zbl 1084.68086 |
| [3] | Carter, N. C., (Visual Group Theory. Visual Group Theory, Classroom Resource Materials Series (2009), Mathematical Association of America: Mathematical Association of America Washington, DC) · Zbl 1194.20001 |
| [4] | Chiswell, I., (A Course in Formal Languages, Automata and Groups. A Course in Formal Languages, Automata and Groups, Universitext (2009), Springer-Verlag London, Ltd.: Springer-Verlag London, Ltd. London) · Zbl 1159.68474 |
| [5] | Coxeter, H. S.M.; Moser, W. O.J., (Generators and Relations for Discrete Groups. Generators and Relations for Discrete Groups, Ergebnisse der Mathematik und ihrer Grenzgebiete, vol. 14 (1980), Springer-Verlag: Springer-Verlag Berlin-New York) · Zbl 0422.20001 |
| [6] | Cunningham, K. K.A.; Edgar, T.; Helminck, A. G.; Jones, B. F.; Oh, H.; Schwell, R.; Vasquez, J. F., On the structure of involutions and symmetric spaces of dihedral groups, Note Mat., 34, 2, 23-40 (2014) · Zbl 1336.20025 |
| [7] | Dummit, D. S.; Foote, R. M., Abstract Algebra (2004), John Wiley & Sons, Inc.: John Wiley & Sons, Inc. Hoboken, NJ · Zbl 1037.00003 |
| [8] | Egri-Nagy, A.; Gebhardt, V.; Tanaka, M. M.; Francis, A. R., Group-theoretic models of the inversion process in bacterial genomes, J. Math. Biol., 69, 1, 243-265 (2014) · Zbl 1293.92015 |
| [9] | Fenrick, M. H., Introduction to the Galois Correspondence (1998), Birkhäuser Boston, Inc.: Birkhäuser Boston, Inc. Boston, MA · Zbl 0889.12001 |
| [10] | Hannenhalli, S.; Pevzner, P. A., Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals, J. ACM, 46, 1, 1-27 (1999) · Zbl 1064.92510 |
| [11] | Humphreys, J. E., (Reflection Groups and Coxeter Groups. Reflection Groups and Coxeter Groups, Cambridge Studies in Advanced Mathematics, vol. 29 (1990), Cambridge University Press: Cambridge University Press Cambridge) · Zbl 0725.20028 |
| [12] | Johnson, D. L., (Presentations of Groups. Presentations of Groups, London Mathematical Society Student Texts, vol. 15 (1997), Cambridge University Press: Cambridge University Press Cambridge) · Zbl 0906.20019 |
| [13] | Moulton, V.; Steel, M., The ‘butterfly effect’ in Cayley graphs with applications to genomics, J. Math. Biol., 65, 6-7, 1267-1284 (2012) · Zbl 1260.20002 |
| [14] | Smith, G.; Tabachnikova, O., (Topics in Group Theory. Topics in Group Theory, Springer Undergraduate Mathematics Series (2000), Springer-Verlag London, Ltd.: Springer-Verlag London, Ltd. London) · Zbl 0953.20001 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
