zbMATH — the first resource for mathematics

On the distance between the expressions of a permutation. (English) Zbl 1227.05013
Summary: We prove that the combinatorial distance between any two reduced expressions of a given permutation of \(\{ 1,\ldots ,n \}\) in terms of transpositions lies in \(O(n^{4})\). We prove that this bound is sharp, and, using a connection with the intersection numbers of certain curves in van Kampen diagrams, we give a practical criterion for proving that the derivations provided by the reversing algorithm of P. Dehornoy [“Groups with a complemented presentation,” J. Pure Appl. Algebra 116, No.1–3, 115–137 (1997; Zbl 0870.20023)] are optimal. We also show the existence of length \(\ell\) expressions of different permutations whose reversing requires \(C\ell ^{4}\) elementary steps.

05A05 Permutations, words, matrices
05E15 Combinatorial aspects of groups and algebras (MSC2010)
68R05 Combinatorics in computer science
Full Text: DOI
[1] M. Autord, Aspects algorithmiques du retournement de mot, Ph.D. Thesis, Université de Caen, 2009.
[2] Björner, A.; Brenti, F., ()
[3] Dehornoy, P., Groups with a complemented presentation, J. pure appl. algebra, 116, 115-137, (1997) · Zbl 0870.20023
[4] Dehornoy, P., On completeness of word reversing, Discrete math., 225, 93-119, (2000) · Zbl 0966.05038
[5] Dehornoy, P.; Wiest, B., On word reversing in braid groups, Int. J. algebra comput., 16, 5, 931-947, (2006) · Zbl 1114.20021
[6] Epstein, D.; Cannon, J.; Holt, D.; Levy, S.; Paterson, M.; Thurston, W., Word processing in groups, (1992), Jones & Bartlett Publ. · Zbl 0764.20017
[7] Garside, F.A., The braid group and other groups, Quart. J. math. Oxford, 20-78, 235-254, (1969) · Zbl 0194.03303
[8] Humphreys, J.E., ()
[9] Lyndon, R.C.; Schupp, P.E., Combinatorial group theory, (1977), Springer-Verlag, (reprinted in 2001) · Zbl 0368.20023
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.