On the distance between the expressions of a permutation
| dc.creator | Autord, Marc | |
| dc.creator | Dehornoy, Patrick | |
| dc.date | 2009-02-18 | |
| dc.date.accessioned | 2026-07-07T12:43:29Z | |
| dc.date.available | 2026-07-07T12:43:29Z | |
| dc.description | 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. | |
| dc.identifier | https://arxiv.org/abs/0902.3074 | |
| dc.identifier | http://arxiv.org/abs/0902.3074 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/220438 | |
| dc.subject | Combinatorics | |
| dc.subject | 20B30, 05E15, 20F55, 20F36 | |
| dc.title | On the distance between the expressions of a permutation | |
| dc.type | text |