On the distance between the expressions of a permutation

Marc Autord, Patrick Dehornoy

Published 2009-02-18Version 1

We prove that the combinatorial distance between any two reduced expressions of a given permutation of {1, ..., n} in terms of transpositions lies in O(n^4), a sharp bound. Using a connection with the intersection numbers of certain curves in van Kampen diagrams, we prove that this bound is sharp, and give a practical criterion for proving that the derivations provided by the reversing algorithm of [Dehornoy, JPAA 116 (1997) 115-197] are optimal. We also show the existence of length l expressions whose reversing requires C l^4 elementary steps.