Set Reconstruction on the Hypercube

Set reconstruction on the hypercube, Discrete Analysis 2017:17, 10 pp.

A well-known open problem in graph theory that goes back to the late 1950s is the so-called reconstruction conjecture. This asks whether it is always possible to determine a graph with $n$ vertices up to isomorphism if you are told what all its induced subgraphs with $n-1$ vertices are, with multiplicity. The answer is known to be yes for graphs of up to 11 vertices, for random graphs, and for graphs with certain properties, but in general the problem is very much open.

One can formulate many questions of a similar flavour, asking what information about substructures of a structure is sufficient to reconstruct the whole structure. One class of such problems is about reconstructing a subset $T$ of a set $S$ that is acted on by a group $G$. The $k$-deck of such a subset is defined to be the set of all subsets of $T$ of size $k$ up to translation by $G$, with multiplicity. (Thus, formally it is a multiset with $\binom{|T|}k$ elements.) Since the $k$-deck determines the $(k-1)$-deck, a natural question to ask is how large $k$ needs to be in order for the $k$-deck of any subset $T$ to determine $T$ (also up to translation by $G$).

This paper answers this question when $G$ is the group $\mathbb Z_2^n$ and acts on itself in the usual way. Rather remarkably, an exact bound is established of $\lfloor{n+1-\log_2(n+1-\log_2(n))}\rfloor$, improving the previous best known upper and lower bounds of $n+1$ and $\lfloor{\frac{n+1}2}\rfloor$. (As the author points out, this formula becomes less mysterious when one learns that it is the largest positive integer $k$ such that $k\leq 2^{n+1-k}$.) The proof of the lower bound is a construction that uses elementary methods, while the proof of the upper bound uses Fourier analysis. In an earlier paper [1], the author answered the corresponding (and easier) question for multisets, where the reconstruction number is $n+1$.

[1] LUKE PEBODY. The reconstructibility of finite abelian groups. Combinatorics, Probability
and Computing, 13 (2004), pp. 867–892.