Reconstructing permutations from identification minors

Publikation: Beitrag in FachzeitschriftForschungsartikelBeigetragenBegutachtung

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

OriginalspracheEnglisch
AufsatznummerP4.20
FachzeitschriftThe Electronic journal of combinatorics
Jahrgang22
Ausgabenummer4
PublikationsstatusVeröffentlicht - 30 Okt. 2015
Peer-Review-StatusJa

Externe IDs

Scopus 84945911548

Schlagworte

Schlagwörter

  • Identification minor, Permutation, Reconstruction problem