Sorting permutations with fixed pinnacle set

Irena Rusu¹

¹Université de Nantes

The electronic journal of combinatorics, Tome 27 (2020) no. 3

Résumé

We give a positive answer to a question raised by Davis et al. (Discrete Mathematics 341, 2018), concerning permutations with the same $\pi_{i-1}<\pi_i>\pi_{i+1}$. The question is: given $\pi,\pi'\in S_n$ with the same pinnacle set $S$, is there a sequence of operations that transforms $\pi$ into $\pi'$ 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'$ 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.

Détail

DOI : 10.37236/9231

Classification : 05A05, 05A15
Mots-clés : balanced reversals