Reconstructing permutations from identification minors
Publikation: Beitrag in Fachzeitschrift › Forschungsartikel › Beigetragen › Begutachtung
Beitragende
Abstract
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.
Details
Originalsprache | Englisch |
---|---|
Aufsatznummer | P4.20 |
Fachzeitschrift | The Electronic journal of combinatorics |
Jahrgang | 22 |
Ausgabenummer | 4 |
Publikationsstatus | Veröffentlicht - 30 Okt. 2015 |
Peer-Review-Status | Ja |
Externe IDs
Scopus | 84945911548 |
---|
Schlagworte
Schlagwörter
- Identification minor, Permutation, Reconstruction problem