On reconstruction of signed permutations distorted by reversal errors (Q2470469): Difference between revisions

The author extends the study of whether permutations distorted by a single reversal error can be reconstructed [Discrete Appl. Math. 155, 2426-2434 (2007; Zbl 1126.05006)] to signed permutations. Reversals take a substring of the signed permutation, reverse it, and switch the signs of its elements. For a signed permutation \(P\), let \(B_r(P)\) be the set of all signed permutations arising from \(P\) by \(r\) reversals. It is proved, that for any \(P\in B_n\) with \(n\geq2\) the minimal number of signed permutations in \(B_1(P)\) which are sufficient to reconstruct \(P\) is equal to 3. Furthermore it is shown, that \(P\) is reconstructible from two signed permutations in \(B_1(P)\) with a probability \(\sim\frac{1}{3}\) if \(n\to\infty\). In case of at most two reversal errors, it is proved that at least \(n(n+1)\) permutations in \(B_2(P)\) are required for reconstructing \(P\). The approach is based on the structure of Cayley graphs.