Reconstructing compositions

Vincent Vatter

doi:10.1016/j.disc.2007.03.081

Reconstructing compositions

Vincent Vatter

Pure Mathematics

Research output: Contribution to journal › Article › peer-review

2 Citations (Scopus)

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 n >= 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. (c) 2007 Elsevier B.V. All rights reserved.

Original language	English
Pages (from-to)	1524-1530
Number of pages	7
Journal	Discrete Mathematics
Volume	308
DOIs	https://doi.org/10.1016/j.disc.2007.03.081
Publication status	Published - 6 May 2008

Keywords

composition
layered permutation
reconstruction
COMPOSITION POSET
MOBIUS FUNCTION

Access to Document

10.1016/j.disc.2007.03.081

EP/C523229/1: Multidisciplinary Critical Mass in Computational Algebra and Applications
Linton, S. A. (PI), Gent, I. P. (CoI), Leonhardt, U. (CoI), Mackenzie, A. (CoI), Miguel, I. J. (CoI), Quick, M. (CoI) & Ruskuc, N. (CoI)
EPSRC
1/09/05 → 31/08/10
Project: Standard

Cite this

@article{ef689f6af0484a56ae9a280299a97696,

title = "Reconstructing compositions",

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 n >= 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. (c) 2007 Elsevier B.V. All rights reserved.",

keywords = "composition, layered permutation, reconstruction, COMPOSITION POSET, MOBIUS FUNCTION",

author = "Vincent Vatter",

year = "2008",

month = may,

day = "6",

doi = "10.1016/j.disc.2007.03.081",

language = "English",

volume = "308",

pages = "1524--1530",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

}

TY - JOUR

T1 - Reconstructing compositions

AU - Vatter, Vincent

PY - 2008/5/6

Y1 - 2008/5/6

N2 - 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 n >= 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. (c) 2007 Elsevier B.V. All rights reserved.

AB - 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 n >= 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. (c) 2007 Elsevier B.V. All rights reserved.

KW - composition

KW - layered permutation

KW - reconstruction

KW - COMPOSITION POSET

KW - MOBIUS FUNCTION

U2 - 10.1016/j.disc.2007.03.081

DO - 10.1016/j.disc.2007.03.081

M3 - Article

SN - 0012-365X

VL - 308

SP - 1524

EP - 1530

JO - Discrete Mathematics

JF - Discrete Mathematics

ER -

Reconstructing compositions

Abstract

Keywords

Access to Document

Fingerprint

Projects

EP/C523229/1: Multidisciplinary Critical Mass in Computational Algebra and Applications

Cite this