Permutation Reconstruction

Abstract

In this paper, we consider the problem of permutation reconstruction. This problem is an analogue of graph reconstruction, a famous question in graph theory. In the case of permutations, the problem can be stated as follows: In all possible ways, delete $k$ entries of the permutation $p=p_1p_2p_3...p_n$ and renumber accordingly, creating $n \choose k$ substrings. How large must $n$ be in order for us to be able to reconstruct $p$ from this multiset of substrings? That is, how large must $n$ be to guarantee that this multiset is unique to $p$? Alternatively, one can look at the sets of substrings created this way. We show that in the case when $k=1$, regardless of whether we consider sets or multisets of these substrings, a random permutation needs to be of length at least five to guarantee reconstruction. This in turn yields an interesting result about the symmetries of the poset of permutations. We also give some partial results in the cases when $k=2$ and $k=3$, and finally we give a lower bound on the length of a permutation for general $k$.