×

zbMATH — the first resource for mathematics

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.
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 Explorer
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[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, Classroom Resource Materials Series, (2009), Mathematical Association of America Washington, DC)
[4] Chiswell, I., (A Course in Formal Languages, Automata and Groups, Universitext, (2009), Springer-Verlag London, Ltd. London) · Zbl 1159.68474
[5] Coxeter, H. S.M.; Moser, W. O.J., (Generators and Relations for Discrete Groups, Ergebnisse der Mathematik und ihrer Grenzgebiete, vol. 14, (1980), 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. 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. 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, Cambridge Studies in Advanced Mathematics, vol. 29, (1990), Cambridge University Press Cambridge) · Zbl 0725.20028
[12] Johnson, D. L., (Presentations of Groups, London Mathematical Society Student Texts, vol. 15, (1997), 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, Springer Undergraduate Mathematics Series, (2000), 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.