Reconstructing Random Jigsaws
Paul Balister, Béla Bollobás, Bhargav P. Narayanan · Oxford University Press eBooks · 2018
The chapter “Reconstructing Random Jigsaws” examines the reconstruction problem for a family of discrete structures, asking whether it is possible to uniquely reconstruct a structure in this family from the “deck” of all its substructures of some fixed size. Reconstruction problems involving combinatorics and randomness have a very rich history. The oldest such problem is perhaps the graph reconstruction conjecture of Kelly and Ulam; analogous questions include reconstructing finite sets satisfying symmetry conditions, reconstructing finite abelian groups, and reconstructing finite subsets of the plane. A natural line of enquiry is to ask how the answer to the reconstruction problem changes when it is necessary to reconstruct a typical (as opposed to an arbitrary) structure in a family of discrete structures. This chapter presents a theoretical case study of interest for all the complex architectures of networks: a reconstruction problem connected with DNA sequencing via the shotgun-sequencing technique.