Metrics on permutations with the same descent set

Abstract

Let $S_n$ be the symmetric group on the set $[n]:=\{1,2,\dots ,n\}$. Given a permutation $\sigma ={\sigma }_1{\sigma }_2\cdots {\sigma }_n\in S_n$, we say it has a descent at index $i$ if ${\sigma }_i>{\sigma }_{i+1}$. Let $\mathcal{D}(\sigma )$ be the set of all descents of $\sigma$ and define $\mathcal{D}(S;n)=\{\sigma \in S_n|\mathcal{D}(\sigma )=S\}$. We study the Hamming metric and ${\ell }_{\infty }$-metric on the sets $\mathcal{D}(S;n)$ for all possible nonempty $S\subset [n-1]$ to determine the maximum possible value that these metrics can achieve when restricted to these subsets.

10 pages, 2 tables