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

Previous talks by year: 2024 2023 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M | admin login