dc.contributor.author Smith, Rebecca dc.date.accessioned 2021-09-07T17:56:25Z dc.date.available 2021-09-07T17:56:25Z dc.date.issued 2006-06-01 dc.identifier.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 . dc.identifier.uri http://hdl.handle.net/20.500.12648/2610 dc.description First published in Electronic Journal of Combinatorics in 2006, published by the American Mathematical Society dc.description.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. dc.title Permutation Reconstruction dc.type article dc.source.journaltitle Electronic Journal of Combinatorics dc.source.volume 13 dc.source.issue 1 refterms.dateFOA 2021-09-07T17:56:25Z dc.description.institution SUNY Brockport dc.source.peerreviewed TRUE dc.source.status published dc.description.publicationtitle Mathematics Faculty Publications dc.contributor.organization The College at Brockport dc.languate.iso en_US
﻿

### Files in this item

Name:
mth_facpub/9/fulltext (1).pdf
Size:
86.52Kb
Format:
PDF