Reconstructing compositions

DOI10.1016/J.DISC.2007.03.081MaRDI QIDQ2477377zbMATH OpenOpenAlexFDO

Authors Vincent Vatter

Publication date 13 March 2008

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0610477

zbMATH Keywords

reconstructioncompositionlayered permutation

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) Combinatorics on words (68R15)

Abstract: We consider the problem of reconstructing compositions of an integer from their subcompositions, which was raised by Raykova (albeit disguised as a question about layered permutations). We show that every composition w of nge 3k+1 can be reconstructed from its set of k-deletions, i.e., the set of all compositions of n-k contained in w. As there are compositions of 3k with the same set of k-deletions, this result is best possible.

Recommendations

• A sharp bound for the reconstruction of partitions
• Reconstruction of partitions
• Permutation reconstruction
• Permutation reconstruction from minors
• Efficient reconstruction of partitions

Cites work

• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 1146222 (Why is no real title available?)
• scientific article; zbMATH DE number 2107707 (Why is no real title available?)
• scientific article; zbMATH DE number 854872 (Why is no real title available?)
• scientific article; zbMATH DE number 3258862 (Why is no real title available?)
• Permutation reconstruction
• Permutation reconstruction from minors
• Rationality of the Möbius function of a composition poset
• Reconstruction of partitions
• Some basic observations on Kelly's conjecture for graphs
• Standard paths in another composition poset
• The Möbius function of a composition poset

Cited in

(8)

• The cutting of compositions
• Composition: a fresh look at an old topic
• A sharp bound for the reconstruction of partitions
• RECONSTRUCTION OF G. SPENCER BROWN'S THEME
• Invitation to composition
• Compositions with distinct parts
• On the dimension of downsets of integer partitions and compositions
• Regenerative composition structures

This page was built for publication: Reconstructing compositions

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