New Upper Bounds on the Size of Permutation Codes under Kendall $\tau$-Metric
| Autor: | Abdollahi, Alireza, Bagherian, Javad, Jafari, Fatemeh, Khatami, Maryam, Parvaresh, Farzad, Sobhani, Reza |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | We first give two methods based on the representation theory of symmetric groups to study the largest size $P(n,d)$ of permutation codes of length $n$ i.e. subsets of the set $S_n$ all permutations on $\{1,\dots,n\}$ with the minimum distance (at least) $d$ under the Kendall $\tau$-metric. The first method is an integer programming problem obtained from the transitive actions of $S_n$. The second method can be applied to refute the existence of perfect codes in $S_n$.\\ Here we reduce the known upper bound $(n-1)!-1$ for $P(n,3)$ to $(n-1)!-\lceil\frac{n}{3}\rceil+2\leq (n-1)!-2$, whenever $n\geq 11$ is any prime number. If $n=6$, $7$, $11$, $13$, $14$, $15$, $17$, the known upper bound for $P(n,3)$ is decreased by $3,3,9,11,1,1,4$, respectively. Comment: arXiv admin note: substantial text overlap with arXiv:2206.10193 |
| Databáze: | arXiv |
| Externí odkaz: |
|