pith. sign in

arxiv: 1907.07250 · v1 · pith:MZ5KRO5Enew · submitted 2019-07-16 · 🧮 math.CO · math.PR

Shotgun reconstruction in the hypercube

Micha{\l} Przykucki , Alexander Roberts , Alex Scott This is my paper

Pith reviewed 2026-05-24 20:38 UTC · model grok-4.3

classification 🧮 math.CO math.PR
keywords hypercuberandom coloringreconstructionballsmultisetBoolean functionsshotgun reconstruction
0
0 comments X

The pith

Almost every random 2-coloring of the hypercube can be reconstructed from the multiset of its radius-2 balls.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines reconstruction of random vertex colorings on the n-dimensional hypercube from the multisets of colorings on small balls. Mossel and Ross posed the general question of when local ball data suffices to recover a global coloring. For uniformly random 2-colorings, the authors establish that radius 2 is already sufficient for almost every coloring. This stands in contrast to worst-case colorings, which require balls whose diameter grows linearly with n. The result further shows that when the number of colors q satisfies q at least n to the power 2 plus epsilon, radius-1 balls suffice for almost every q-coloring.

Core claim

The central claim is that almost every random 2-coloring of the hypercube vertices is the unique coloring that produces any given multiset of radius-2 ball colorings. Equivalently, for random Boolean functions, the multiset of all radius-2 restrictions determines the function with high probability. When the number of colors grows at least as fast as n to the power 2 plus a positive constant, the same uniqueness holds already for the multiset of radius-1 balls.

What carries the argument

The multiset of induced colorings on all balls of a fixed small radius, from which the global coloring is recovered via uniqueness arguments for random instances.

If this is right

  • Almost every 2-coloring admits unique reconstruction from its radius-2 multiset.
  • For q at least n to the power 2 plus epsilon, almost every q-coloring is uniquely determined by its radius-1 multiset.
  • Typical random colorings require far smaller radius than the Omega(n) diameter needed in the worst case.
  • The reconstruction threshold for random colorings is constant rather than linear in dimension.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Efficient algorithms could iterate over candidate global colorings consistent with observed local multisets and verify uniqueness in polynomial time for random instances.
  • The same local-to-global uniqueness may hold for other highly symmetric graphs such as strong products or Cayley graphs on groups with suitable expansion.
  • One could test the finite-n threshold by enumerating all 2-colorings of small hypercubes and measuring the fraction that collide under the radius-2 multiset map.
  • The result suggests studying how the required radius scales with the number of colors between the constant and polynomial regimes.

Load-bearing premise

The coloring is chosen uniformly at random by assigning each vertex an independent uniform color.

What would settle it

An explicit family of pairs of distinct 2-colorings of the hypercube, each pair sharing the same multiset of radius-2 ball colorings, whose total measure does not tend to zero with dimension n would falsify the claim.

read the original abstract

Mossel and Ross raised the question of when a random colouring of a graph can be reconstructed from local information, namely the colourings (with multiplicity) of balls of given radius. In this paper, we are concerned with random $2$-colourings of the vertices of the $n$-dimensional hypercube, or equivalently random Boolean functions. In the worst case, balls of diameter $\Omega(n)$ are required to reconstruct. However, the situation for random colourings is dramatically different: we show that almost every $2$-colouring can be reconstructed from the multiset of colourings of balls of radius $2$. Furthermore, we show that for $q \ge n^{2+\epsilon}$, almost every $q$-colouring can be reconstructed from the multiset of colourings of $1$-balls.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper studies reconstruction of random colorings of the n-dimensional hypercube from the multiset of local ball colorings. It proves that almost every uniform random 2-coloring is uniquely recoverable w.h.p. from the multiset of radius-2 ball colorings. It further shows that for q-colorings with q ≥ n^{2+ε}, almost every such coloring is recoverable from the multiset of radius-1 ball colorings. The worst-case requirement of diameter-Ω(n) balls is contrasted with these average-case results.

Significance. If the claims hold, the results sharply separate worst-case from random-case reconstruction thresholds on the hypercube, advancing the Mossel-Ross program on local reconstruction from multisets of balls. The explicit radius-2 threshold for 2-colorings and the polynomial dependence on n for q-colorings are concrete contributions to probabilistic combinatorics and coding theory.

minor comments (2)
  1. The abstract and introduction should explicitly state the probability space (uniform random independent coloring) and the high-probability quantification (1-o(1) as n→∞) to avoid ambiguity with the worst-case statement.
  2. Notation for the multiset of ball colorings and the precise meaning of 'reconstructed' (unique recovery up to automorphism or exact vertex labeling) should be fixed in §1 before the main theorems.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, significance assessment, and recommendation of minor revision. No major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper proves a probabilistic reconstruction theorem for random colorings of the hypercube: with high probability a uniform random 2-coloring is uniquely recoverable from the multiset of its radius-2 balls (and an analogous statement for q-colorings when q is large). The derivation relies on direct combinatorial-probabilistic arguments applied to the uniform random model stated in the abstract; no parameter is fitted to data and then re-used as a prediction, no self-citation supplies a load-bearing uniqueness theorem, and the central claim is not equivalent by construction to its inputs. The result is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No free parameters, axioms, or invented entities are identifiable from the abstract alone.

pith-pipeline@v0.9.0 · 5664 in / 972 out tokens · 19267 ms · 2026-05-24T20:38:33.846684+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages · 4 internal anchors

  1. [1]

    N. Alon, Y. Caro, I. Krasikov, and Y. Roditty. Combinatorial rec onstruction problems. Journal of Combinatorial Theory, Series B , 47:153–161, 1989

    work page 1989

  2. [2]

    Balister, B

    P. Balister, B. Bollob´ as, and B. Narayanan. Reconstructing ra ndom jigsaws. In S. Bat- tiston, G. Caldarelli, and A. Garas, editors, Multiplex and Multilevel Networks , pages 31–50. Oxford University Press, 2018. 34

    work page 2018

  3. [3]

    Benjamini and H

    I. Benjamini and H. Kesten. Distinguishing sceneries by observin g the scenery along a random walk path. Journal d’Analyse Math´ ematique, 69:97–135, 1996

    work page 1996

  4. [4]

    Bollob´ as

    B. Bollob´ as. Almost every graph has reconstruction number th ree. Journal of Graph Theory, 14:1–4, 1990

    work page 1990

  5. [5]

    J. Bondy. A graph reconstructor’s manual. In A. D. Keedwell, ed itor, Surveys in Combinatorics, pages 221–252. Cambridge University Press, 1991

    work page 1991

  6. [6]

    Shotgun Assembly of Random Jigsaw Puzzles

    C. Bordenave, U. Feige, and E. Mossel. Shotgun assembly of ran dom jigsaw puzzles. arXiv:1605.03086, preprint, May 2016

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  7. [7]

    Indistinguishable sceneries on the Boolean hypercube

    R. Gross and U. Grupel. Indistinguishable sceneries on the Boolea n hypercube. arXiv:1701.07667, preprint, January 2017

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  8. [8]

    Hajnal and E

    A. Hajnal and E. Szemer´ edi. Proof of a Conjecture of Erd˝ os . Combinatorial Theory and Its Applications , pages 601–623, 1970

    work page 1970

  9. [9]

    F. Harary. On the reconstruction of a graph from a collection of subgraphs. Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963 ), Publ. House Czechoslovak Acad. Sci., Prague , pages 47–52, 1964

    work page 1963

  10. [10]

    L. Harper. Optimal numberings and isoperimetric problems on gr aphs. Journal of Combinatorial Theory , 1:385–393, 1996

    work page 1996

  11. [11]

    Keane and W

    M. Keane and W. T. F. den Hollander. Ergodic properties of color records. Physica A, 138:183–193, 1986

    work page 1986

  12. [12]

    Stability for vertex isoperimetry in the cube

    P. Keevash and E. Long. Stability for vertex isoperimetry in the cube. arXiv:1807.09618, preprint, July 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  13. [13]

    P. J. Kelly. A congruence theorem for trees. Pacific Journal of Mathematics , 7:961–968, 1957

    work page 1957

  14. [14]

    Lauri and R

    J. Lauri and R. Scapellato. Topics in graph automorphisms and reconstruction . Cam- bridge University Press, 2016

    work page 2016

  15. [15]

    Lov´ asz.Combinatorial problems and exercises

    L. Lov´ asz.Combinatorial problems and exercises . North-Holland Publishing Co., second edition, 1993

    work page 1993

  16. [16]

    A linear threshold for uniqueness of solutions to random jigsaw puzzles

    A. Martinsson. A linear threshold for uniqueness of solutions to random jigsaw puzzles. arXiv:1701.04813, preprint, January 2017

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  17. [17]

    Mitzenmacher and E

    M. Mitzenmacher and E. Upfal. Probability and Computing . Cambridge University Press, 2017

    work page 2017

  18. [18]

    Mossel and N

    E. Mossel and N. Ross. Shotgun assembly of labeled graphs. IEEE Transactions on Network Science and Engineering , 2017. 35

    work page 2017

  19. [19]

    Mossel and N

    E. Mossel and N. Sun. Shotgun assembly of random regular gra phs. arXiv:1512.08473, preprint, December 2015

    work page arXiv 2015

  20. [20]

    C. St. J. A. Nash-Williams. The reconstruction problem. In L. Be ineke and R. Wilson, editors, Selected topics in graph theory , pages 205–236. Academic Press, 1978

    work page 1978

  21. [21]

    Nenadov, P

    R. Nenadov, P. Pfister, and A. Steger. Unique reconstructio n threshold for random jigsaw puzzles. Chicago Journal of Theoretical Computer Science , 2:1–16, 2017

    work page 2017

  22. [22]

    Pebody, J

    L. Pebody, J. Radcliffe, and A. Scott. Finite subsets of the plan e are 18-reconstructible. SIAM Journal of Discrete Mathematics , 16:262–275, 2003

    work page 2003

  23. [23]

    Przykucki and A

    M. Przykucki and A. Roberts. Vertex-isoperimetric stability in the hypercube. arXiv:1808.02572, preprint, August 2018

    work page arXiv 2018

  24. [24]

    Radcliffe and A

    J. Radcliffe and A. Scott. Reconstructing subsets of Zn. Journal of Combinatorial Theory, Series A , 83:169–187, 1998

    work page 1998

  25. [25]

    J. Simon. The combinatorial k-deck. Graphs and Combinatorics , 34:1597–1618, 2018

    work page 2018

  26. [26]

    S. M. Ulam. A collection of mathematical problems . Interscience Tracts in Pure and Applied Mathematics, no. 8. Interscience Publishers, New York-Lo ndon, 1960

    work page 1960

  27. [27]

    van Hintum

    P. van Hintum. Locally biased partitions of Zn. European Journal of Combinatorics , pages 262–270, 2019. 36

    work page 2019