Reconstructing random jigsaws

A colouring of the edges of an $n\times n$ 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 $n \times n$gridarecolouredindependentlyanduniformlyatrandomusing$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\mathrm{/}3})$ and from above, Bordenave, Feige and Mossel and Nenadov, Pfister and Steger independently showed, for any fixed $ϵ>0$, that such a colouring is reconstructible when $q \ge n^{1+\epsilon}$. Here, we improve on these results and prove the following: there exist absolute constants $C,c>0$ such that, as $n\to \mathrm{\infty }$, the probability that a random colouring as above is reconstructible tends to $1$ if $q\ge Cn$ and to $0$ if $q\le cn$.