ON THE DISTANCE BETWEEN THE EXPRESSIONS OF A PERMUTATION

Abstract. We prove that the combinatorial distance between any two re-duced expressions of a given permutation of {1,..., n} in terms of transposi-tions lies in O(n4), 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 pro-vided by the reversing algorithm of [Dehornoy, JPAA 116 (1997) 115-197] are optimal. We also show the existence of length ` expressions whose reversing requires C`4 elementary steps. This paper is about the various ways of expressing a permutation as a product of transpositions and the complexity of transforming one such expression into an-other. We consider both the absolute complexity (“combinatorial distance”), which deals with the minimal possible number of steps, and the more specific complexity (“reversing complexity”), which arises when one uses subword reversing, a certain prescribed strategy for transforming expressions. Throughout the paper, we denote by [[1, n]] the set {1, 2,..., n}, and by si th