Permutation reconstruction from a few large patterns (Q2049616)

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)].