A Linear Threshold for Uniqueness of Solutions to Random Jigsaw Puzzles. (8th January 2019)

• Record Type: Journal Article
• Authors: MARTINSSON, ANDERS
• Is Part Of: Combinatorics, probability and computing. Volume 28:Number 2(2019)
• Page Start: 287
• Page End: 302
• Publication Date: 2019-01-08
• Subjects: Primary 60C05, -- Secondary 05C10; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548318000391
• Languages: English
• ISSNs: 0963-5483

Abstract

Abstract : We consider a problem introduced by Mossel and Ross ('Shotgun assembly of labeled graphs', arXiv:1504.07682 ). Suppose a random n × 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 a global rotation of the puzzle, 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 ⩽ q ⩽ 2 e −1/2 n, all solutions are similar when q ⩾ (2+ϵ) n, and the solution is unique when q = ω( n ).