2023/01/26 by Sergey Bereg, Bereg, Sergey, William Bumpass +7
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · #Coding theory and cryptography #Combinatorics (math.CO) #DNA and Biological Computing #FOS: Mathematics #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2301.11423
openalex publication_date 2023/01/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Permutation arrays under the Kendall-τ metric have been considered for error-correcting codes. Given n and d∈ [1..\binomn2], the task is to find a large permutation array of permutations on n symbols with pairwise Kendall-τ distance at least d. Let P(n,d) denote the maximum size of any permutation array of permutations on n symbols with pairwise Kendall-τ distance d. New algorithms and several theorems are presented, giving improved lower bounds for P(n,d). Also, (n,m,d)-arrays are defined, which are permutation arrays on n symbols with Kendall-τ distance d, with the restriction that symbols 1...(n-m) appear in increasing order. Let P(n,m,d) denote the maximum size of any (n,m,d)-array. For example, (n,m,d)-arrays are useful for recursively computing lower bounds for P(n,d). Lower and upper bounds are given for P(n.m,d).