Premium
Shotgun reconstruction in the hypercube
Author(s) -
Przykucki Michał,
Roberts Alexander,
Scott Alex
Publication year - 2022
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.21028
Subject(s) - multiset , hypercube , combinatorics , mathematics , multiplicity (mathematics) , graph , discrete mathematics , geometry
Mossel and Ross raised the question of when a random coloring of a graph can be reconstructed from local information, namely, the colorings (with multiplicity) of balls of given radius. In this article, we are concerned with random 2‐colorings of the vertices of the n ‐dimensional hypercube, or equivalently random Boolean functions. In the worst case, balls of diameter Ω ( n ) are required to reconstruct. However, the situation for random colorings is dramatically different: we show that almost every 2‐coloring can be reconstructed from the multiset of colorings of balls of radius 2. Furthermore, we show that for q ≥ n 2 + ϵ, almost every q ‐coloring can be reconstructed from the multiset of colorings of 1‐balls.