Bounds on the size of balls over permutations with the infinity metric Conference Paper uri icon


  • We study the size (or volume) of balls in the metric space of permutations, S n , under the infinity metric. We focus on the regime of balls with radius r = ρ · (n-1), ρ ∈ [0, 1], i.e., a radius that is a constant fraction of the maximum possible distance. We provide new bounds on the size of such balls. These bounds reduce the asymptotic gap between the upper and lower bound to at most 0.06 bits per symbol.

publication date

  • January 1, 2015