Representing permutations with few moves

DOI10.1137/15M1036105MaRDI QIDQ2827490zbMATH OpenOpenAlexFDO

Authors Sergey Bereg, A. E. Holroyd, Lev Nachmanson, Sergey Pupyrev

Publication date 20 October 2016

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

permutation graph drawing permutation pattern reduced word permutation diagram

Permutations, words, matrices (05A05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: Consider a finite sequence of permutations of the elements 1,...,n, with the property that each element changes its position by at most 1 from any permutation to the next. We call such a sequence a tangle, and we define a move of element i to be a maximal subsequence of at least two consecutive permutations during which its positions form an arithmetic progression of common difference +1 or -1. We prove that for any initial and final permutations, there is a tangle connecting them in which each element makes at most 5 moves, and another in which the total number of moves is at most 4n. On the other hand, there exist permutations that require at least 3 moves for some element, and at least 2n-2 moves in total. If we further require that every pair of elements exchange positions at most once, then any two permutations can be connected by a tangle with at most O(log n) moves per element, but we do not know whether this can be reduced to O(1) per element, or to O(n) in total. A key tool is the introduction of certain restricted classes of tangle that perform pattern-avoiding permutations.

Recommendations

Cites work

Cited in

(5)

This page was built for publication: Representing permutations with few moves

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