Reconstructing infinite sets of integers
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.
- Reconstructing integer sets from their representation functions
- Reconstructing infinite objects
- Infinite subsets of random sets of integers
- Reconstructing subsets of reals
- Computing sets from all infinite subsets
- Reconstructing subsets of \(\mathbb{Z}_n\)
- Reconstruction of infinite graphs
- Infinite sumsets with many representations
- Reconstructing the number of blocks of an infinite graph
- A congruence theorem for trees
- Combinatorial reconstruction problems
- scientific article; zbMATH DE number 3141308 (Why is no real title available?)
- scientific article; zbMATH DE number 17789 (Why is no real title available?)
- scientific article; zbMATH DE number 1029242 (Why is no real title available?)
- scientific article; zbMATH DE number 1146222 (Why is no real title available?)
- scientific article; zbMATH DE number 3258862 (Why is no real title available?)
- On Kelly's lemma for infinite sets of integers
- Reconstructing subsets of \(\mathbb{Z}_n\)
- Reconstructing subsets of reals
- The k-orbit reconstruction and the orbit algebra
- The \(k\)-orbit reconstruction for Abelian and Hamiltonian groups
- A sharp bound for the reconstruction of partitions
- Reconstructing subsets of \(\mathbb{Z}_n\)
- A note on the reconstruction of sets of finite measure
- Reconstruction of functions from their triple correlations
- Reconstructing infinite objects
- The combinatorial \(k\)-deck
- Reconstruction of a coloring from its homogeneous sets
- scientific article; zbMATH DE number 1792624 (Why is no real title available?)
- The Reconstructibility of Finite Abelian Groups
- On the determination of sets by their triple correlation in finite cyclic groups
This page was built for publication: Reconstructing infinite sets of integers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q696913)
