A linear threshold for uniqueness of solutions to random jigsaw puzzles

Abstract

We consider a problem introduced by Mossel and Ross [Shotgun assembly of labeled graphs, arXiv:1504.07682]. Suppose a random $n\times n$ jigsaw puzzle is constructed by independently and uniformly choosing the shape of each "jig" from $q$ possibilities. We are given the shuffled pieces. Then, depending on $q$, what is the probability that we can reassemble the puzzle uniquely? We say that two solutions of a puzzle are similar if they only differ by permutation of duplicate pieces, and rotation of rotationally symmetric pieces. In this paper, we show that, with high probability, such a puzzle has at least two non-similar solutions when $2\le q\le \frac{2}{\sqrt{e}}n$, all solutions are similar when $q\ge (2+\epsilon )n$, and the solution is unique when $q=\omega (n)$.

15 pages, 3 figures. A weaker form of part (i) of Theorem 1.1 was shown by myself in arXiv:1605.07151v2. It is restated here with a much simpler proof, as a part of the main result

Cited by in corpus (2)

• Reconstructing random pictures
• Shotgun assembly of random graphs