Permutation reconstruction from a few large patterns
The authors consider a reconstruction problem in permutation combinatorics. Given a permutation \(\pi_1 \dots \pi_n \in S_n\), an \((n-1)\)-pattern is by definition an element of \(S_{n-1}\) obtained by deletion of one \(\pi_i\) and order-preserving rearrangement of the remaining numbers. The author shows that every permutation of size at least \(5\) is reconstructible from a set of \((n-1)\)-patterns, if this set has cardinality at least \(\lceil n/2 \rceil + 2\). This is analogous to a famous unsolved problem in graph theory posed by \textit{P. J. Kelly} [On isometric transformations. University of Wisconsin (PhD Thesis) (1942)] and \textit{S. M. Ulam} [A collection of mathematical problems. Interscience Publishers, New York, NY (1960; Zbl 0086.24101)].
- Reconstruction of permutations from their erroneous patterns
- Permutation reconstruction
- Permutation reconstruction from differences
- On reconstructing a hidden permutation
- Permutation reconstruction from MinMax-betweenness constraints
- Permutations containing many patterns
- Reconstruction of permutations distorted by reversal errors
- The computational landscape of permutation patterns
- Patterns in random permutations
- Reconstruction Algorithm for Permutation Graphs
- Determining a permutation from its set of reductions.
- scientific article; zbMATH DE number 3141308 (Why is no real title available?)
- scientific article; zbMATH DE number 2107707 (Why is no real title available?)
- Patterns in permutations and words.
- Permutation reconstruction
- Permutation reconstruction from minors
This page was built for publication: Permutation reconstruction from a few large patterns
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2049616)
