Seminar Details
Reconstructing Random Pictures
- Start Date: March 8, 2023
- Event Start Time: 12:15 PM
- Event End Time: 1:15 PM
- Seminar Series: Graduate Combinatorics Seminar
- Presenter(s): Corrine Yap - Rutgers University
- Event Location: Mathematics Graduate Student Lounge -- 7th Floor | Rutgers University | Hill Center | Mathematics Department
- Event Additional Info: <p>Also Presented Via Zoom: <a href="https://rutgers.zoom.us/j/91649887793?pwd=MDB4aXdYUytERWUxZ0xhUk53bURUUT09">https://rutgers.zoom.us/j/91649887793?pwd=MDB4aXdYUytERWUxZ0xhUk53bURUUT09</a> </p> <p>Meeting ID: 916 4988 7793</p> <p>Password: gcs2023</p> <p>See: <a href="https://sites.math.rutgers.edu/~kmg326/GCS/GCS.html">https://sites.math.rutgers.edu/~kmg326/GCS/GCS.html</a></p>
- Presentation Type: Stand Alone Presentation
- Abstract:
Reconstruction problems ask whether or not it is possible to uniquely build a discrete structure from the collection of its substructures of a fixed size. This question has been explored in a wide range of settings, most famously with graphs and the resulting Graph Reconstruction Conjecture due to Kelly and Ulam, but also including geometric sets, jigsaws, and abelian groups. In this talk, we'll consider the reconstruction of random pictures (n-by-n grids with binary entries) from the collection of its k-by-k subgrids and prove a nearly-sharp threshold for k = k(n). Our main proof technique is an adaptation of the Peierls contour method from statistical physics.
Joint work with Bhargav Narayanan.