@article{bereg2015representing,
author = {Bereg, Sergey and Holroyd, Alexander E. and Nachmanson, Lev and Pupyrev, Sergey},
title = {Representing Permutations with Few Moves},
year = {2015},
month = {August},
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.},
publisher = {Cornell University Library},
url = {http://approjects.co.za/?big=en-us/research/publication/representing-permutations-moves/},
}