Permutation reconstruction from minors

Mariana Raykova

The electronic journal of combinatorics, Tome 13 (2006)

Résumé

We consider the problem of permutation reconstruction, which is a variant of graph reconstruction. Given a permutation $p$ of length $n$, we delete $k$ of its entries in each possible way to obtain ${n \choose k}$ subsequences. We renumber the sequences from $1$ to $n-k$ preserving the relative size of the elements to form $(n-k)$-minors. These minors form a multiset $M_k(p)$ with an underlying set $M_k'(p)$. We study the question of when we can reconstruct $p$ from its multiset or its set of minors. We prove there exists an $N_k$ for every $k$ such that any permutation with length at least $N_k$ is reconstructible from its multiset of $(n-k)$-minors. We find the bounds $N_k > k+\log_2 k$ and $N_k < {k^2\over4} + 2k + 4$. For the number $N_k'$, giving the minimal length for permutations to be reconstructible from their sets of $(n-k)$-minors, we have the bound $N_k' > 2k$. We work towards analogous bounds in the case when we restrict ourselves to layered permutations.

Détail

DOI : 10.37236/1092

Classification : 05A05
Mots-clés : subsequences, multiset