1-ball reconstruction threshold gap in Qₙ

Gap problem for 1-ball reconstruction threshold · arXiv:1907.07250

arXiv Problem medium confidence— first stated 2019-07-16

Authors: Michał Przykucki, Alexander Roberts, Alex Scott

Status open high confidence

The conjecture asks to narrow the gap between the Omega(n) lower bound and the n^{2+epsilon} upper bound for the threshold number of colours q*(n) at which almost every q-colouring of Q_n becomes reconstructible from its multiset of coloured 1-balls. The source paper (published in Random Structures & Algorithms 60, 2022) established these two bounds, but no subsequent paper has been found that closes or significantly narrows this gap. Related shotgun assembly work on lattice models and random graphs has appeared, but none addresses the hypercube 1-ball threshold directly.

Reviewer notes. No follow-up resolving or narrowing the gap was found in five web calls. The source paper appeared in Random Structures & Algorithms 60(1) 117-150 (2022). Nearby literature found includes arXiv:2205.01327 (shotgun threshold for lattice labeling model, Z^d not Q_n) and a 2025 Springer paper on shotgun assembly of random graphs — neither addresses the Q_n 1-ball colour threshold. The arXiv paper 2308.01671 ('Reconstruction of graph colourings') concerns k-deck reconstruction on grids and random graphs, not 1-ball coloring reconstruction on Q_n. The problem remains open with high confidence.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Problem. Determine the correct threshold $q^*(n)$ such that almost every $q$-colouring of the hypercube $Q_n$ is reconstructible from the multiset of its coloured 1-balls, narrowing the gap between the lower bound $q = \Omega(n)$ and the upper bound $q \geq n^{2+\varepsilon}$.

Context

Theorem 1.2 shows that for $q \geq n^{2+\varepsilon}$ almost every $q$-colouring of $Q_n$ is 1-distinguishable, while a counting argument shows that $\Omega(n)$ colours are necessary for reconstruction from 1-balls. The authors note explicitly that 'it would be interesting to narrow the gap', with further discussion deferred to Section 6 (open questions).

Notes. Stated informally in the introduction without a labelled environment: 'It is easy to show that Ω(n) colours are required for reconstructability, and it would be interesting to narrow the gap (see Sections 1.1 and 6 for further discussion).' Section 6, which reportedly contains further open questions, was not included in the provided text extract.

Source paper

Shotgun reconstruction in the hypercube
Michał Przykucki, Alexander Roberts, Alex Scott · 2019-07-16
https://arxiv.org/abs/1907.07250 PDF source