Published by the Department of Computer Science, The University of Chicago.

Abstract

A random jigsaw puzzle is constructed by arranging $n^2$ square pieces into an $n \times n$ grid and assigning to each edge of a piece one of $q$ available colors uniformly at random, with the restriction that touching edges receive the same color. We show that if $q = o(n)$ then with high probability such a puzzle does not have a unique solution, while if $q \ge n^{1 + \varepsilon}$ for any constant $\varepsilon > 0$ then the solution is unique. This solves a conjecture of Mossel and Ross ( Shotgun assembly of labeled graphs, arXiv:1504.07682).

• The article: PDF (338 KB)
• Source material: ZIP (445 KB)
• BibTeX entry for this article (297 bytes)

Submitted October 21, 2017, revised May 22, 2017, in final form June 29, 2017 published June 30, 2017.

© 2017 Rajko Nenadov, Pascal Pfister and Angelika Steger
Licensed under a Creative Commons Attribution License

Volume 2017, Article 1

Volume 2018 Article 1

Volume 2017

Published articles