On the distance between the expressions of a permutation

DOI10.1016/J.EJC.2010.03.003MaRDI QIDQ709253zbMATH OpenOpenAlexFDO

Authors Patrick Dehornoy, Marc Autord

Publication date 18 October 2010

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0902.3074

zbMATH Keywords

combinatorial distance

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorics in computer science (68R05)

Abstract: 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.

Recommendations

• Edit Distances and Factorisations of Even Permutations
• Lower bounding edit distances between permutations
• Distance in cayley graphs on permutation groups generated by $k$ $m$-Cycles
• Analysis of reversal and transposition distances for permutations
• Combinatorial Pattern Matching

Cites work

• scientific article; zbMATH DE number 47598 (Why is no real title available?)
• scientific article; zbMATH DE number 53661 (Why is no real title available?)
• scientific article; zbMATH DE number 3574107 (Why is no real title available?)
• Combinatorics of Coxeter Groups
• Groups with a complemented presentation
• ON WORD REVERSING IN BRAID GROUPS
• On completeness of word reversing
• THE BRAID GROUP AND OTHER GROUPS

Cited in

(16)

• Sublinear time algorithms in the theory of groups and semigroups.
• scientific article; zbMATH DE number 4168690 (Why is no real title available?)
• Extending a word property for twisted Coxeter systems
• Distances in graphs of permutations
• The subword reversing method.
• Diameter of graphs of reduced words and galleries.
• Diameter of the commutation classes graph of a permutation
• The minimum Manhattan distance and minimum jump of permutations
• An inversion statistic for reduced words
• The height of a permutation and applications to distance between real line arrangements
• Permutation Arrays Under the Chebyshev Distance
• scientific article; zbMATH DE number 4177065 (Why is no real title available?)
• Diameter of a commutation class on reduced words
• On maximal chains in the non-crossing partition lattice
• Diameters of graphs of reduced words and rank-two root subsystems
• On the action of permutations on distances between values of rational functions mod \(p\)

This page was built for publication: On the distance between the expressions of a permutation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q709253)