Reconstructing sequences (Q1377760)

Let \(S\) be a binary sequence of length \(n\). Then \(S\) contains \(\left(\begin{smallmatrix} n\\ k\end{smallmatrix}\right)\) subsequences of length \(k\). The multiset of these subsequences is called the \(k\)-deck of \(S\). Further, if \(S\) is uniquely defined by its \(k\)-deck, then \(S\) is called \(k\)-reconstructible. For a fixed positive integer \(n\), let \(f(n)\) be the smallest \(k\) such that every binary sequence of length \(n\) is \(k\)-reconstructible. \textit{B. Manvel}, \textit{A. Meyerowitz}, \textit{A. Schwenk}, \textit{K. Smith} and \textit{P. Stockmeyer} [Discrete Math. 94, No. 3, 209-219 (1991; Zbl 0746.05045)] proved that if \(n\geq 7\), then \(f(n)\leq [n/2]\). In the present paper the author improves that: \(f(n)\leq (1+o(1))\sqrt{n\log n}\).