Metrics on permutations with the same peak set

Abstract

Let $S_n$ be the symmetric group on the set $\{1,2,\dots ,n\}$. Given a permutation $\sigma ={\sigma }_1{\sigma }_2\cdots {\sigma }_n\in S_n$, we say it has a peak at index $i$ if ${\sigma }_{i-1}<{\sigma }_i>{\sigma }_{i+1}$. Let $\text{Peak}(\sigma )$ be the set of all peaks of $\sigma$ and define $P(S;n)=\{\sigma \in S_n|\text{Peak}(\sigma )=S\}$. In this paper we study the Hamming metric, ${\ell }_{\infty }$-metric, and Kendall-Tau metric on the sets $P(S;n)$ for all possible $S$, and determine the minimum and maximum possible values that these metrics can attain in these subsets of $S_n$.

7 pages, 3 tables