On the distance between the expressions of a permutation

Marc Autord, Patrick Dehornoy

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…