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

reconstruction algorithmk-deletionsreconstruction of partitions

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Combinatorial aspects of partitions of integers (05A17) 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.

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)

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

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)