2015/08/14 by Sergey Bereg, Alexander E. Holroyd, Bereg, Sergey +5
Mathematics · #05A05 #05D99 #68R10 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05A05 #msc:05D99 #msc:68R10
paper · pdf · doi:10.48550/arxiv.1508.03674
arxiv created 2015/08/14 · arxiv updated 2015/08/18
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.