A Linear Threshold for Uniqueness of Solutions to Random Jigsaw Puzzles

DOI10.1017/S0963548318000391MaRDI QIDQ5219322zbMATH OpenFDO

Authors Anders Martinsson

Publication date 11 March 2020

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1701.04813

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Combinatorial probability (60C05)

Abstract: We consider a problem introduced by Mossel and Ross [Shotgun assembly of labeled graphs, arXiv:1504.07682]. Suppose a random $nimesn$ 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 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 $2leqqleqfrac2sqrten$, all solutions are similar when $qgeq(2+varepsilon)n$, and the solution is unique when $q=omega(n)$.

Recommendations

• Unique reconstruction threshold for random jigsaw puzzles
• The satisfiability threshold for random linear equations
• A sharp threshold for a random constraint satisfaction problem
• The threshold for jigsaw percolation on random graphs
• A general model and thresholds for random constraint satisfaction problems
• The satisfiability threshold for a seemingly intractable random constraint satisfaction problem
• scientific article; zbMATH DE number 5688296
• scientific article; zbMATH DE number 6469137

Cites work

• Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity
• Unique reconstruction threshold for random jigsaw puzzles

Cited in

(13)

• Solving scramble squares puzzles with repetitions
• Shotgun assembly of Erdős-Rényi random graphs
• No easy puzzles: hardness results for jigsaw puzzles
• scientific article; zbMATH DE number 5688296 (Why is no real title available?)
• Finding a unique solution to Radon-Kaczmarz puzzles
• Shotgun assembly of random jigsaw puzzles
• Solving jigsaw puzzles by the graph connection Laplacian
• Unique reconstruction threshold for random jigsaw puzzles
• Shotgun reconstruction in the hypercube
• Shotgun assembly threshold for lattice labeling model
• An algorithm to recover shredded random matrices
• Shotgun assembly of unlabeled Erdős-Rényi graphs
• Reconstructing random pictures

This page was built for publication: A Linear Threshold for Uniqueness of Solutions to Random Jigsaw Puzzles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5219322)