Reconstructing infinite sets of integers (Q696913): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: Robert R. Molina / rank | |||
Property / reviewed by | |||
Property / reviewed by: Robert R. Molina / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1006/jcta.2002.3271 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2074918462 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Combinatorial reconstruction problems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3975132 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4386292 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5544087 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A congruence theorem for trees / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The \(k\)-orbit reconstruction and the orbit algebra / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4343052 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The \(k\)-orbit reconstruction for Abelian and Hamiltonian groups / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Reconstructing subsets of \(\mathbb{Z}_n\) / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Reconstructing subsets of reals / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On Kelly's lemma for infinite sets of integers / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3259049 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 17:03, 4 June 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