Loading...
Journal Title
Electronic Journal of Combinatorics
Keywords
Readers/Advisors
Journal Title
Term and Year
Publication Date
2006-06-01
Book Title
Publication Volume
13
Publication Issue
1
Publication Begin
Publication End
Number of pages
Collections
Files
Research Projects
Organizational Units
Journal Issue
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 = p1p2p3 . . . pn and renumber accordingly,creating (n/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 ? 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 partialresults in the cases when = 2 and k = 3, and finally we give a lower bound on the length of a permutation for general k.
Citation
Smith, R. Permutation Reconstruction, Electronic Journal of Combinatorics, 13 (1), 2006. Available on publisher's site at http://www.esaim-cocv.org/10.1017/S0017089505002466 .
DOI
Description
First published in Electronic Journal of Combinatorics in 2006, published by the American Mathematical Society