### Volume 2017

#### Unique reconstruction threshold for random jigsaw puzzles

School of Mathematical Sciences
Monash University
Melbourne, Australia
rajko DOT nedanov AT monash DOT edu

Pascal Pfister
Institute of Theoretical Computer Science
ETH
Zurich, Switzerland
ppfister AT inf DOT ethz DOT ch

and

Angelika Steger
Institute of Theoretical Computer Science
ETH
Zurich,Switzerland
steger AT inf DOT ethz DOT ch

June 30, 2017

#### 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)