On the distance between the expressions of a permutation

DOI10.1016/J.EJC.2010.03.003zbMATH Open1227.05013arXiv0902.3074OpenAlexW2110761667MaRDI QIDQ709253FDOQ709253

Marc Autord, Patrick Dehornoy

Publication date: 18 October 2010

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

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.

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

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

zbMATH Keywords

combinatorial distance

Mathematics Subject Classification ID

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

Cites Work

• Combinatorics of Coxeter Groups
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• THE BRAID GROUP AND OTHER GROUPS
• Groups with a complemented presentation
• On completeness of word reversing
• ON WORD REVERSING IN BRAID GROUPS

Cited In (15)

• Diameter of graphs of reduced words and galleries.
• Diameter of a commutation class on reduced words
• The height of a permutation and applications to distance between real line arrangements
• Permutation Arrays Under the Chebyshev Distance
• The minimum Manhattan distance and minimum jump of permutations
• Diameter of the commutation classes graph of a permutation
• An inversion statistic for reduced words
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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\)
• Extending a word property for twisted Coxeter systems
• On maximal chains in the non-crossing partition lattice
• Sublinear time algorithms in the theory of groups and semigroups.
• THE SUBWORD REVERSING METHOD

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)