Sorting permutations with fixed pinnacle set

DOI10.37236/9231zbMATH Open1445.05006arXiv2001.08417OpenAlexW3082047108MaRDI QIDQ785571FDOQ785571

Authors: Irena Rusu 

Publication date: 7 August 2020

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: We give a positive answer to a question raised by Davis et al. ({em Discrete Mathematics} 341, 2018), concerning permutations with the same pinnacle set. Given $piin{S}_n$, a {em pinnacle} of $pi$ is an element $p{i}_i$ ($ieq1,n$) such that $p{i}_{i-1}<p{i}_i>p{i}_{i+1}$. The question is: given $pi,p{i}^{\prime }in{S}_n$ with the same pinnacle set $S$, is there a sequence of operations that transforms $pi$ into $p{i}^{\prime }$ such that all the intermediate permutations have pinnacle set $S$? We introduce {em balanced reversals}, defined as reversals that do not modify the pinnacle set of the permutation to which they are applied. Then we show that $pi$ may be sorted by balanced reversals (i.e. transformed into a standard permutation $I{d}_S$), implying that $pi$ may be transformed into $p{i}^{\prime }$ using at most $4n-2minp,3$ balanced reversals, where $p=|S|geq1$. In case $p=0$, at most $2n-1$ balanced reversals are needed.

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

Recommendations

• A formula for enumerating permutations with a fixed pinnacle set
• Pinnacle set properties
• Pinnacle sets of signed permutations
• The pinnacle set of a permutation
• Admissible pinnacle orderings

zbMATH Keywords

balanced reversals

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15)

Cites Work

• Permutations with given peak set
• Peak quasisymmetric functions and Eulerian enumeration
• New results on the peak algebra.
• Counting descents, rises, and levels, with prescribed first element, in words
• \(\log\)-lists and their applications to sorting by transpositions, reversals and block-interchanges
• The pinnacle set of a permutation
• Efficient data structures and a new randomized approach for sorting signed permutations by reversals
• A proof of the peak polynomial positivity conjecture
• Value-peaks of permutations

Cited In (7)

• Efficient recurrence for the enumeration of permutations with fixed pinnacle set
• Permutations with given peak set
• Pinnacle sets of signed permutations
• A formula for enumerating permutations with a fixed pinnacle set
• Pinnacle set properties
• Admissible pinnacle orderings
• Further results on pinnacle sets

This page was built for publication: Sorting permutations with fixed pinnacle set

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