Reconstructing random jigsaws

arXiv1707.04730MaRDI QIDQ6289034FDOQ6289034

Authors: Paul Balister, Béla Bollobás, Bhargav P. Narayanan 

Publication date: 15 July 2017

Abstract: A colouring of the edges of an $nimesn$ grid is said to be emph{reconstructible} if the colouring is uniquely determined by the multiset of its $n^2$ emph{tiles}, where the tile corresponding to a vertex of the grid specifies the colours of the edges incident to that vertex in some fixed order. In 2015, Mossel and Ross asked the following question: if the edges of an $nimesn$ grid are coloured independently and uniformly at random using $q=q(n)$ different colours, then is the resulting colouring reconstructible with high probability? From below, Mossel and Ross showed that such a colouring is not reconstructible when $q=o(n^{2/3})$ and from above, Bordenave, Feige and Mossel and Nenadov, Pfister and Steger independently showed, for any fixed $epsilon>0$, that such a colouring is reconstructible when $qge{n}^{1+epsilon}$. Here, we improve on these results and prove the following: there exist absolute constants $C,c>0$ such that, as $noinfty$, the probability that a random colouring as above is reconstructible tends to $1$ if $qgeCn$ and to $0$ if $qlecn$.

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Combinatorial probability (60C05) Combinatorics on words (68R15)

This page was built for publication: Reconstructing random jigsaws

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6289034)