Metrics on Permutations With the Same Descent Set

Abstract

A permutation in a finite symmetric group on a set of ordered elements has a descent at the i-th index if the permutation value at the i-th index is greater than the permutation value that follows. The descent set of a permutation is the set of all indices where the permutation has a descent. Each finite symmetric group can be partitioned by descent sets. In this paper we study the Hamming metric and the L-infinity metric on the sets of permutations that share the same descent set for all nonempty descent sets to determine the maximum possible value that these metrics can achieve when restricted to these subsets.