Reconstructing Young tableaux
A \(k\)-minor of a standard Young tableau (SYT) \(T\) with \(n\) entries is an SYT with \(n-k\) entries that is obtained from \(T\) via a certain jeu-de-taquin process. The authors consider the problem of reconstruction, which asks whether a given SYT is uniquely determined once we know some of its minors. M. M. Gillespie [\textit{M. Monks}, J. Comb. Theory, Ser. A 116 (1) 76--91 (2009; Zbl 1228.05047)] asked for which values of \(n\) and \(k\) can every SYT with \(n\) entries be reconstructed from its set of \(k\)-minors. This paper takes a first step towards the resolution of Gillespie's question. The main result is that any SYT \(T\) with at least \(5\) entries can be reconstructed from its set of \(1\)-minors. The authors prove this by induction. First, they show that the set of \(1\)-minors of \(T\) determines the shape of \(T\) when \(n\ge 3\) and the location of the largest entry of \(T\) when \(n\ge 4\). Then, after removing the largest entry of \(T\), the authors show that the \(1\)-minors of the resulting tableau are determined by the minors of \(T\). These results combined with several base cases are sufficient to show the result. From here, it is a simple case check to show precisely which SYT are reconstructable from their sets of \(1\)-minors, and also answer the slightly different question of which SYT are reconstructable from their multisets of \(1\)-minors. The authors close by suggesting a further question: in the case where \(T\) is reconstructable by its multiset of \(k\)-minors, how many minors are necessary? They show a first result, that when \(n\ge 5\) and \(k=1\), there exist SYT where at least \(\lfloor n/2\rfloor + 2\) minors are needed.
- A congruence theorem for trees
- A sharp bound for the reconstruction of partitions
- scientific article; zbMATH DE number 1001729 (Why is no real title available?)
- scientific article; zbMATH DE number 3141308 (Why is no real title available?)
- scientific article; zbMATH DE number 1146222 (Why is no real title available?)
- Reconstruction of partitions
- The solution to the partition reconstruction problem
This page was built for publication: Reconstructing Young tableaux
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2068618)
