Reconstructing permutations from identification minors

MaRDI QIDQ888635zbMATH OpenFDO

Authors Erkko Lehtonen

Publication date 2 November 2015

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p20

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

identification minorpermutationreconstruction problem

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Review text

Summary: 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.

Recommendations

• Permutation reconstruction from minors
• Reconstructing permutations from cycle minors
• Permutation reconstruction from MinMax-betweenness constraints
• On reconstructing a hidden permutation
• Permutation reconstruction from differences
• Reconstruction of permutations from their erroneous patterns
• Permutation reconstruction
• Reconstructing convex permutominoes
• scientific article; zbMATH DE number 1538179
• Minimal permutations with \(d\) descents

Cites work

• A complete classification of equational classes of threshold functions included in clones
• A congruence theorem for trees
• Boolean minors
• Characterizations of closed classes of Boolean functions in terms of forbidden subfunctions and Post classes
• Determining a permutation from its set of reductions.
• Equational characterizations of Boolean function classes
• Essential arities of term operations in finite algebras
• Galois theory for minors of finite functions
• scientific article; zbMATH DE number 3141308 (Why is no real title available?)
• Hypomorphic Sperner systems and non-reconstructible functions
• On closed sets of relational constraints and classes of functions closed under variable substitutions
• On the size of an infinite language
• Permutation reconstruction
• Permutation reconstruction from minors
• RECONSTRUCTING MULTISETS OVER COMMUTATIVE GROUPOIDS AND AFFINE FUNCTIONS OVER NONASSOCIATIVE SEMIRINGS
• Reconstructing permutations from cycle minors
• Set-reconstructibility of Post classes

Cited in

(10)

• Reconstructing permutations from cycle minors
• Hypomorphic Sperner systems and non-reconstructible functions
• A dual Ramsey theorem for permutations
• Permutation reconstruction from minors
• Permutation reconstruction
• Ramsey properties of products and pullbacks of categories and the Grothendieck construction
• Permutation reconstruction from MinMax-betweenness constraints
• Determining a permutation from its set of reductions.
• The minor order of homomorphisms via natural dualities
• Improvements on permutation reconstruction from minors

This page was built for publication: Reconstructing permutations from identification minors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q888635)