New Results on the Reconstruction of Permutations Distorted By Single Kendall <italic>&#x03C4;</italic>-Errors

Abstract

The reconstruction problem for permutations on $n$ elements from their erroneous patterns which are distorted by single Kendall $\tau $ -errors was presented by Konstantinova et al. in 2007. To date, some authors solved some cases where the transmitted permutation can be arbitrary and the erroneous patterns are distorted by at most two or three Kendall $\tau $ -errors. In this paper, we study the setup where the transmitted permutation on $n$ elements can be arbitrary and the erroneous patterns are distorted by at most four Kendall $\tau $ -errors. In this scenario, it is shown that $\frac {n^{3}-n-3}{3}$ erroneous patterns are needed to reconstruct an unknown permutation from an arbitrary unknown permutation for any $n\geq 9$ .

Keywords

• Kendall τ-errors
• permutation codes
• sequence reconstruction