Set Reconstruction on the Hypercube

Luke Pebody

Discrete analysis (2017)

Résumé

Given an action of a group $G$ on a set $S$, the $k$-deck of a subset $T$ of $S$ is the multiset of all subsets of $T$ of size $k$, each given up to translation by $G$. For a given subset $T$, the {\em reconstruction number} of $T$ is the minimum $k$ such that the $k$-deck uniquely identifies $T$ up to translation by $G$, and the {\em reconstruction number} of the action $G:S$ is the maximum reconstruction number of any subset of $S$. The concept of reconstruction number extends naturally to multisubsets $T$ of $S$ and in~\cite{CPC:257539}, the author calculated the multiset-reconstruction number of all finite abelian groups. In particular, it was shown that the multiset-reconstruction number of $\mathbb{Z}_2^n$ was $n+1$. This provides an upper bound of $n+1$ to the reconstruction number of $\mathbb{Z}_2^n$. The author also showed a lower bound of $\lfloor{\frac{n+1}2}\rfloor$ in the same paper. The purpose of this note is to close the gap. The reconstruction number of $\mathbb{Z}_2^n$ is $\lfloor{n+1-\log_2(n+1-\log_2(n))}\rfloor.$

Détail

Publié le : 2017-10-27