Geodesic
Reconstructing permutations from identification minors
Erkko Lehtonen1
1Technische Universität Dresden
The electronic journal of combinatorics, Tome 22 (2015) no. 4
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/5353
Classification : 05A05
Mots-clés : reconstruction problem, permutation, identification minor

Erkko Lehtonen  1

1 Technische Universität Dresden 
@article{10_37236_5353,
     author = {Erkko Lehtonen},
     title = {Reconstructing permutations from identification minors},
     journal = {The electronic journal of combinatorics},
     year = {2015},
     volume = {22},
     number = {4},
     doi = {10.37236/5353},
     zbl = {1323.05009},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/5353/}
}
TY  - JOUR
AU  - Erkko Lehtonen
TI  - Reconstructing permutations from identification minors
JO  - The electronic journal of combinatorics
PY  - 2015
VL  - 22
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/5353/
DO  - 10.37236/5353
ID  - 10_37236_5353
ER  - 
%0 Journal Article
%A Erkko Lehtonen
%T Reconstructing permutations from identification minors
%J The electronic journal of combinatorics
%D 2015
%V 22
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/5353/
%R 10.37236/5353
%F 10_37236_5353
Erkko Lehtonen. Reconstructing permutations from identification minors. The electronic journal of combinatorics, Tome 22 (2015) no. 4. doi: 10.37236/5353

Cité par Sources :