Representing permutations with few moves

DOI10.1137/15M1036105zbMATH Open1347.05002arXiv1508.03674OpenAlexW2962792295MaRDI QIDQ2827490FDOQ2827490

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)

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.

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

Recommendations

• Drawing permutations with few corners
• Short proofs for cut-and-paste sorting of permutations
• Sorting by short block-moves
• Equivalence relations of permutations generated by constrained transpositions
• Equivalence classes of permutations under various relations generated by constrained transpositions

zbMATH Keywords

permutationgraph drawingpermutation patternreduced wordpermutation diagram

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The Yang-Baxter equation, symmetric functions, and Schubert polynomials
• Title not available (Why is that?)
• Symmetric functions, Schubert polynomials and degeneracy loci. Transl. from the French by John R. Swallow
• Title not available (Why is that?)
• Some combinatorial properties of Schubert polynomials
• Drawing Permutations with Few Corners
• Edge routing with ordered bundles
• Patterns in permutations and words.
• Sorting in \(c \log n\) parallel steps
• Proof of a conjecture of Burr, Grünbaum, and Sloane
• On the fully commutative elements of Coxeter groups
• Cell Growth Problems
• Sorting a bridge hand
• Random sorting networks
• RC-Graphs and Schubert Polynomials
• Improving layered graph layouts with edge bundling
• Compositions of pattern restricted sets of permutations
• Ringing the Cosets

Cited In (4)

• Notice of Removal: A Novel Representation for Permutations
• The complexity of finding tangles
• Computing height-optimal tangles faster
• Title not available (Why is that?)

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)