Reconstructing subsets of \(\mathbb{Z}_n\)
type: Item
instance of: scholarly article
title: Reconstructing subsets of \(\mathbb{Z}_n\)
zbMATH Open document ID: 0909.05011
published in: Journal of Combinatorial Theory. Series A
publication date: 1999-03-30T00:00:00Z
review text: Let \(\mathbb{Z}_n\) denote the cyclic group of order \(n\). Say that two subsets of \(\mathbb{Z}_n\) have the same shape if one is the translate of the other. For \(A\subset \mathbb{Z}_n\) with \(| A| \geq k\), the \(k\)-deck of \(A\) is the multiset of shapes of \(k\)-subsets of \(A\). Sets of the same shape have identical \(k\)-decks. The paper is concerned with the reconstruction of shapes: the problem is when is a shape determined by its \(k\)-deck. The results are the following: if \(n\) is prime, then every shape (with at least 3 elements) is reconstructible from its 3-deck, for every \(n\) almost all shapes are reconstructible from their 3-decks, and for every \(n\) all shapes (with at least \(9\alpha (n)\) elements) are reconstructible from their \(9\alpha (n)\)-decks, where \(\alpha (n)\) denotes the number of distinct prime factors of \(n\). Generalizations are also considered.
reviewed by: László A. Székely
Mathematics Subject Classification ID: 05A99
Mathematics Subject Classification ID: 05C60
zbMATH DE Number: 1212976
zbMATH Keywords: reconstruction of shapes
Wikidata QID: Q56213624
author: Andrew John Radcliffe
author: Alex Scott
MaRDI profile type: Publication
full work available at URL: jcta.1998.2870
OpenAlex ID: W2059499591
cites work: Combinatorial reconstruction problems
cites work: Q3975132
cites work: Graph reconstruction—a survey
cites work: Q4386292
cites work: Q4873725
cites work: On a lemma of Littlewood and Offord
cites work: Q3856819
cites work: Q4044675
cites work: On a lemma of Littlewood and Offord on the distribution of certain sums
cites work: A family of non-reconstructible hypergraphs
cites work: On a reconstruction problem for sequences
cites work: Towards the reconstruction of posets
cites work: The \(k\)-orbit reconstruction and the orbit algebra
cites work: Application d'une propriété combinatoire des parties d'un ensemble aux groupes et aux rélations
cites work: Reconstructing sequences
cites work: A census of non-reconstructable digraphs. I: Six related families
DOI: 10.1006/JCTA.1998.2870
description: scientific article; zbMATH DE number 1212976