A sharp bound for the reconstruction of partitions

MaRDI QIDQ1010680zbMATH OpenFDO

Authors Vincent Vatter

Publication date 7 April 2009

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

Full work available at URL https://arxiv.org/abs/0806.3739, https://eudml.org/doc/129814, http://www.emis.de/journals/EJC/Volume_15/Abstracts/v15i1n23.html

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

k-deletionsreconstruction algorithmreconstruction of partitions

Mathematics Subject Classification ID

Combinatorial aspects of partitions of integers (05A17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Combinatorics of partially ordered sets (06A07)

Abstract: Answering a question of Cameron, Pretzel and Siemons proved that every integer partition of $nge2(k+3)(k+1)$ can be reconstructed from its set of $k$-deletions. We describe a new reconstruction algorithm that lowers this bound to $nge{k}^2+2k$ and present examples showing that this bound is best possible.

Review text

Summary: Answering a question of \textit{P.J. Cameron} [Stories from the age of reconstruction, Congr. Numerantium 113, 31--41 (1996; Zbl 0895.05044)], \textit{O. Pretzel} and \textit{J. Siemons} [Reconstruction of partitions, Electron. J. Comb. 11, No.\,2, Res. Pap. N5 (2004--2005; Zbl 1077.05009)] proved that every integer partition of \(n\geq 2(k+3)(k+1)\) can be reconstructed from its set of \(k\)-deletions. We describe a new reconstruction algorithm that lowers this bound to \(n\geq k^2+2k\) and present examples showing that this bound is best possible.

Recommendations

• Reconstruction of partitions
• Efficient reconstruction of partitions
• The solution to the partition reconstruction problem
• Reconstructing compositions
• Reconstructing infinite sets of integers

Cited in

(9)

• The solution to the partition reconstruction problem
• Efficient reconstruction of partitions
• Recovering nonuniform planted partitions via iterated projection
• Reconstructing Young tableaux
• Reconstructing compositions
• Reconstruction of partitions
• scientific article; zbMATH DE number 1305516 (Why is no real title available?)
• On Shattering, Splitting and Reaping Partitions
• Young tableau reconstruction via minors

This page was built for publication: A sharp bound for the reconstruction of partitions

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