Diametric problem for permutations with the Ulam metric (optimal anticodes)

We study the diametric problem (i. e. , optimal anticodes) in the space of permutations under the Ulam distance. That is, let Sₙ denote the set of permutations on n symbols, and for each, Sₙ, 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 2^k + C k^{2/3} n! / (n-k) !, compared to the best known construction of size n!/ (n-k) !. We also prove that sets of diameter 1 have at most n elements.