Publicações > Artigos em Revistas Internacionais

Reconstructing permutations from identification minors

Lehtonen, Erkko

Electronic Journal of Combinatorics, 22(4) (2015), #P4.20

We consider the problem whether a permutation of a finite set is uniquely determined by its identification minors. While there exist non-reconstructible permutations of every set with two, three, or four elements, we show that every permutation of a finite set with at least five elements is reconstructible from its identification minors. Moreover, we provide an algorithm for recovering a permutation from its deck. We also discuss a generalization of this reconstruction problem, as well as the related set-reconstruction problem.