Sorting Permutations with Fixed Pinnacle Set

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 $\pi \in S_n$, a {\em pinnacle} of $\pi$ is an element ${\pi }_i$ ($i\ne 1,n$) such that ${\pi }_{i-1}<{\pi }_i>{\pi }_{i+1}$. The question is: given $\pi ,{\pi }^{\prime }\in S_n$ with the same pinnacle set $S$, is there a sequence of operations that transforms $\pi$ into ${\pi }^{\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 $\Id_S$), implying that $\pi$ may be transformed into ${\pi }^{\prime }$ using at most $4n-2\min \{p,3\}$ balanced reversals, where $p=|S|\ge 1$. In case $p=0$, at most $2n-1$ balanced reversals are needed.

18 pages, 1 figure