{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,5]],"date-time":"2025-06-05T15:04:05Z","timestamp":1749135845483},"reference-count":8,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2019,1,8]],"date-time":"2019-01-08T00:00:00Z","timestamp":1546905600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2019,3]]},"abstract":"<jats:p>We consider a problem introduced by Mossel and Ross (\u2018Shotgun assembly of labeled graphs\u2019, <jats:monospace>arXiv:1504.07682<\/jats:monospace>). Suppose a random <jats:italic>n<\/jats:italic> \u00d7 <jats:italic>n<\/jats:italic> jigsaw puzzle is constructed by independently and uniformly choosing the shape of each \u2018jig\u2019 from <jats:italic>q<\/jats:italic> possibilities. We are given the shuffled pieces. Then, depending on <jats:italic>q<\/jats:italic>, 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 \u2a7d <jats:italic>q<\/jats:italic> \u2a7d 2<jats:italic>e<\/jats:italic><jats:sup>\u22121\/2<\/jats:sup><jats:italic>n<\/jats:italic>, all solutions are similar when <jats:italic>q<\/jats:italic> \u2a7e (2+\u03f5)<jats:italic>n<\/jats:italic>, and the solution is unique when <jats:italic>q<\/jats:italic> = \u03c9(<jats:italic>n<\/jats:italic>).<\/jats:p>","DOI":"10.1017\/s0963548318000391","type":"journal-article","created":{"date-parts":[[2019,1,8]],"date-time":"2019-01-08T15:41:11Z","timestamp":1546962071000},"page":"287-302","source":"Crossref","is-referenced-by-count":8,"title":["A Linear Threshold for Uniqueness of Solutions to Random Jigsaw Puzzles"],"prefix":"10.1017","volume":"28","author":[{"given":"ANDERS","family":"MARTINSSON","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2019,1,8]]},"reference":[{"key":"S0963548318000391_ref5","unstructured":"Martinsson A. (2016) Shotgun edge assembly of random jigsaw puzzles. arXiv:1605.07151"},{"key":"S0963548318000391_ref7","doi-asserted-by":"publisher","DOI":"10.4086\/cjtcs.2017.002"},{"key":"S0963548318000391_ref1","unstructured":"Balister P. , Bollob\u00e1s B. and Narayanan B. (2017) Reconstructing random jigsaws. In Multiplex and Multilevel Networks, Oxford University Press, to appear, ISBN 9780198809456"},{"key":"S0963548318000391_ref6","doi-asserted-by":"publisher","DOI":"10.1109\/TNSE.2017.2776913"},{"key":"S0963548318000391_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-007-0713-4"},{"key":"S0963548318000391_ref2","unstructured":"Bordenave C. , Feige U. and Mossel E. (2016) Shotgun assembly of random jigsaw puzzles. arXiv:1605.03086"},{"key":"S0963548318000391_ref3","doi-asserted-by":"publisher","DOI":"10.2197\/ipsjjip.25.682"},{"key":"S0963548318000391_ref8","unstructured":"PR Newswire, 16 February 2007, description of Eternity II release: http:\/\/www.prnewswire.co.uk\/news-releases\/eternity-puzzle-is-back-this-summer-with-a-us2-million-prize-for-the-first-person-to-find-a-solution-153539245.html"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548318000391","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,12]],"date-time":"2019-04-12T19:03:12Z","timestamp":1555095792000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548318000391\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1,8]]},"references-count":8,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,3]]}},"alternative-id":["S0963548318000391"],"URL":"https:\/\/doi.org\/10.1017\/s0963548318000391","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1,8]]}}}