Reconstructing infinite sets of integers (Q696913): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 10:54, 30 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Reconstructing infinite sets of integers |
scientific article |
Statements
Reconstructing infinite sets of integers (English)
0 references
12 September 2002
0 references
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.
0 references
reconstruction
0 references
integers
0 references