Sharp-threshold conjecture for reconstructibility of random jigsaws
Let be the random -jigsaw, and let reconstructibility mean that the jigsaw is uniquely determined by its deck. The critical number of colours is conjectured to be asymptotic to . Sharp-threshold conjecture. For every , as ,
for all . The complementary -statement, namely that reconstructibility has probability tending to below the critical threshold, is established in the paper for . The conjecture predicts the sharp transition location, while the upper statement remains open in the interval between and the proved linear upper bound.
References
- Paul Balister, Béla Bollobás and Bhargav Narayanan, “Reconstructing random jigsaws”, arXiv:1707.04730 (2017).
Progress summary
Never refreshed
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.