Sorting Permutations with Fixed Pinnacle Set

January 23, 2020 Β· Declared Dead Β· πŸ› Electronic Journal of Combinatorics

πŸ‘» CAUSE OF DEATH: Ghosted
No code link whatsoever

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Irena Rusu arXiv ID 2001.08417 Category cs.DS: Data Structures & Algorithms Cross-listed math.CO Citations 6 Venue Electronic Journal of Combinatorics Last Checked 4 months ago
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 $Ο€\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.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

πŸ“œ Similar Papers

In the same crypt β€” Data Structures & Algorithms

Died the same way β€” πŸ‘» Ghosted