Sorting Permutations with Fixed Pinnacle Set

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

No reviews yet.

No comments yet.