 ## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Thursday, March 31, 2016, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Pascal Pfister

## A threshold for the identifiability of the $n \times n$ random jigsaw puzzle

The jigsaw Puzzle is given by an $n \times n$ grid $G$ of puzzle pieces, where each puzzle piece has exactly four edges associated to it. Each pair of adjacent edges of the puzzle is coloured uniformly and independently at random from one of $q$ colors (edges adjacent to the border of the grid get coloured as well). We assume that two pieces can be joined at two of their edges if and only if both of these edges have the same colour. The problem then is the following: given a stack of $n^2$ coloured puzzle pieces, is it possible to find the original composition $G$ of the puzzle? Or formulated differently, how large does $q$ need to be so that the only possible reconstruction of the puzzle pieces is the original puzzle itself?

We show the following:
i) if $q = o(n)$ then the probability of unique reconstruction goes to 0 as $n \rightarrow \infty$, and
ii) for every $0 < \epsilon < 1/4$: if $q \geq n^{1+ \epsilon}$ then the probability of unique reconstruction goes to 1 as $n \rightarrow \infty$.

This result solves a conjecture of Mossel and Ross from their paper "Shotgun assembly of labeled graphs" (recall Mossel's Mittagseminar talk from last Oktober).

Upcoming talks     |     All previous talks     |     Talks by speaker     | Upcoming talks in iCal format (beta version!)

Information for students and suggested topics for student talks