تقرير
Diametric problem for permutations with the Ulam metric (optimal anticodes)
| العنوان: | Diametric problem for permutations with the Ulam metric (optimal anticodes) |
|---|---|
| المؤلفون: | Devlin, Pat, Douhovnikoff, Leo |
| سنة النشر: | 2024 |
| المجموعة: | Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics, 05D05, 05A05, 05C35, 05C69 |
| الوصف: | We study the diametric problem (i.e., optimal anticodes) in the space of permutations under the Ulam distance. That is, let $S_n$ denote the set of permutations on $n$ symbols, and for each $\sigma, \tau \in S_n$, 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. Comment: 11 pages |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2403.02276 |
| رقم الأكسشن: | edsarx.2403.02276 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |