Unique reconstruction threshold for random jigsaw puzzles

DOI10.4086/CJTCS.2017.002MaRDI QIDQ5360828zbMATH OpenOpenAlexFDO

Authors Rajko Nenadov, Pascal Pfister, Angelika Steger

Publication date 26 September 2017

Published in Chicago Journal of Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

graph reconstructionjigsaw puzzle

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Abstract: A random jigsaw puzzle is constructed by arranging $n^2$ square pieces into an $nimesn$ grid and assigning to each edge of a piece one of $q$ available colours uniformly at random, with the restriction that touching edges receive the same colour. We show that if $q=o(n)$ then with high probability such a puzzle does not have a unique solution, while if $qge{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).

Recommendations

• A Linear Threshold for Uniqueness of Solutions to Random Jigsaw Puzzles
• Shotgun assembly of random jigsaw puzzles
• No easy puzzles: hardness results for jigsaw puzzles
• Multi-coloured jigsaw percolation on random graphs
• Solving jigsaw puzzles by the graph connection Laplacian

Cited in

(11)

• Solving scramble squares puzzles with repetitions
• Shotgun assembly of Erdős-Rényi random graphs
• No easy puzzles: hardness results for jigsaw puzzles
• Finding a unique solution to Radon-Kaczmarz puzzles
• Shotgun assembly of random jigsaw puzzles
• Solving jigsaw puzzles by the graph connection Laplacian
• A Linear Threshold for Uniqueness of Solutions to Random Jigsaw Puzzles
• Shotgun reconstruction in the hypercube
• 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: Unique reconstruction threshold for random jigsaw puzzles

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