Reconstructing Subsets of Reals

  • A. J. Radcliffe
  • A. D. Scott

Abstract

We consider the problem of reconstructing a set of real numbers up to translation from the multiset of its subsets of fixed size, given up to translation. This is impossible in general: for instance almost all subsets of $\mathbb{Z}$ contain infinitely many translates of every finite subset of $\mathbb{Z}$. We therefore restrict our attention to subsets of $\mathbb{R}$ which are locally finite; those which contain only finitely many translates of any given finite set of size at least 2.

We prove that every locally finite subset of $\mathbb{R}$ is reconstructible from the multiset of its 3-subsets, given up to translation.

Published
1999-03-15
Article Number
R20