Reconstructing infinite sets of integers
type: Item
instance of: scholarly article
title: Reconstructing infinite sets of integers
zbMATH Open document ID: 1007.05073
author: Dieter Rautenbach
author: Eberhard Triesch
published in: Journal of Combinatorial Theory. Series A
publication date: 2002-09-12T00:00:00Z
review text: This paper deals with the problem of reconstructing an infinite set of integers form its collection of subsets of cardinality \(k\). This problem is related to the famous reconstruction conjectures for finite graphs; see \textit{J. A. Bondy} [Lond. Math. Soc. Lect. Note Ser. 166, 221-252 (1991; Zbl 0741.05052)]. Let \(\mathbb{Z}\) denote the set of integers, and for \(A\subseteq \mathbb{Z}\) let \(A\choose k\) denote the set of all subsets of \(A\) of cardinality \(k\). Two sets \(A,B\subseteq \mathbb{Z}\) are called isomorphic if \(A+i=\{a+i:a\in A\}=B\) for some \(i\in\mathbb{Z}\), and we write \(A\approx B\). The \(k\)-deck of \(A\) is the function \(d_{A,k}:{A\choose k}\to \mathbb{Z}\) defined by \(d_{A,k}(S)=|\{i\in \mathbb{Z}:S+i\subseteq A\}|\). The set \(A\) is said to be reconstructible from its \(k\)-deck if \(d_{A,k}=d_{B,k}\) implies that \(A\approx B\). Note that if \(A\) is an infinite set, then \(d_{A,k}\) may take infinite values. If \(d_{A,k}\) takes only finite values, then \(A\) is said to be \(k\)-finite. It is easy to see that finite sets are reconstructible from their \(k\)-decks for all \(k\geq 3\), but reconstruction of infinite sets is more interesting. The main result of this paper is that if \(k\geq 3\) and \(A\subseteq\mathbb{Z}\) is \(k\)-finite, infinite, and has the property that \(0< d_{A,k-1}(S)<\infty\) for some \(S\in{\mathbb{Z}\choose k-1}\), then \(A\) is reconstructible form its \(k\)-deck. It is also shown that a set \(A\) need not be reconstructible from its \(k\)-deck if the condition that the \((k-1)\)-deck takes at least one finite non-zero value is not satisfied. In this sense the result is the best possible.
Mathematics Subject Classification ID: 05C60
zbMATH DE Number: 1800279
zbMATH Keywords: reconstruction
zbMATH Keywords: integers
reviewed by: Robert R. Molina
MaRDI profile type: Publication
full work available at URL: jcta.2002.3271
OpenAlex ID: W2074918462
cites work: Combinatorial reconstruction problems
cites work: Q3975132
cites work: Q4386292
cites work: Q5544087
cites work: A congruence theorem for trees
cites work: The \(k\)-orbit reconstruction and the orbit algebra
cites work: Q4343052
cites work: The \(k\)-orbit reconstruction for Abelian and Hamiltonian groups
cites work: Reconstructing subsets of \(\mathbb{Z}_n\)
cites work: Reconstructing subsets of reals
cites work: On Kelly's lemma for infinite sets of integers
cites work: Q3259049
DOI: 10.1006/JCTA.2002.3271
Recommended article: Reconstructing integer sets from their representation functions
Recommended article: Reconstructing infinite objects
Recommended article: Infinite subsets of random sets of integers
Recommended article: Reconstructing subsets of reals
Recommended article: Computing sets from all infinite subsets
Recommended article: Reconstructing subsets of \(\mathbb{Z}_n\)
Recommended article: Reconstruction of infinite graphs
Recommended article: Infinite Sumsets with Many Representations
Recommended article: Reconstructing the number of blocks of an infinite graph
description: scientific article; zbMATH DE number 1800279