Reconstructing Permutations from Cycle Minors

Abstract

The $i$th cycle minor of a permutation $p$ of the set $\{1,2,\ldots,n\}$ is the permutation formed by deleting an entry $i$ from the decomposition of $p$ into disjoint cycles and reducing each remaining entry larger than $i$ by $1$. In this paper, we show that any permutation of $\{1,2,\ldots,n\}$ can be reconstructed from its set of cycle minors if and only if $n\ge 6$. We then use this to provide an alternate proof of a known result on a related reconstruction problem.