| Summary: | 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 Ω(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 ≥ n 2+∈ , almost every q-colouring can be reconstructed from the multiset of colourings of 1-balls.
|
|---|