Diametric Problem For Permutations With The Ulam Metric (Optimal Anticodes)

Document Type

Article

Publication Date

5-2025

Published In

Journal Of Combinatorial Theory, Series A

Abstract

We study the diametric problem (i.e., optimal anticodes) in the space of permutations under the Ulam distance. That is, let Sn denote the set of permutations on n symbols, and for each σ,τ∈Sn, define their Ulam distance as the number of distinct symbols that must be deleted from each until they are equal. We obtain a near-optimal upper bound on the size of the intersection of two balls in this space, and as a corollary, we prove that a set of diameter at most k has size at most 2k+Ck2/3n!/(n−k)!, compared to the best known construction of size n!/(n−k)!.

Keywords

Permutations, Isodiametric problem, Anticodes, Ulam distance, Deletion distance, Longest common subsequence, Rank modulation, Translocations

This document is currently not available here.

Share

COinS