Permutation reconstruction
Summary: 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\dots 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\).
- The solution to the partition reconstruction problem
- Reconstructing permutations from cycle minors
- Reconstruction of sequences
- Coding for locality in reconstructing permutations
- Permutations resilient to deletions
- Permutation reconstruction from a few large patterns
- Recursive inversion models for permutations
- Growth rates of permutation classes: categorization up to the uncountability threshold
- Equipopularity classes in the separable permutations
- Prolific permutations and permuted packings: downsets containing many large patterns
- Reconstruction of permutations distorted by reversal errors
- Reconstructing compositions
- Permutation reconstruction from minors
- Permutation reconstruction from MinMax-betweenness constraints
- Reconstructing convex permutominoes
- Reconstruction of matrices from submatrices
- Reconstruction Algorithm for Permutation Graphs
- Permutation reconstruction from differences
- A note on statistical averages for oscillating tableaux
- Determining a permutation from its set of reductions.
- Reconstruction of permutations from their erroneous patterns
- Improvements on permutation reconstruction from minors
- Reconstruction of caterpillar tanglegrams
- Reconstructing permutations from identification minors
This page was built for publication: Permutation reconstruction
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2501000)
