The University College London (UCL) Combinatorics Seminar takes place weekly on Monday, from 4pm to 5pm, for location see individual talks. It is organised by Shoham Letzter.

To subscribe to the mailing list, please email Shoham Letzter at s [dot] letzter [at] ucl [dot] ac [dot] uk.

Next Speaker

• 4 December 2023 - Gal Kronenberg (Oxford)

  Shotgun reconstruction of random graphs.

  
  

  We say that a graph $G$ is reconstructible from its $r$-neighbourhoods if all graphs $H$ having the same collection of $r$-balls as $G$ up to isomorphism, are isomorphic to $G$. We are interested in the reconstruction of the Erdős–Renyi random graph $G(n,p)$ for a wide range of values of $r$, aiming to determine the values of $p$ for which $G(n, p)$ is $r$-reconstructible with high probability. Mossel and Ross showed that the the graph $G(n,p)$ can be reconstructed from its 3-neighbourhoods with high probability provided that $p \gg \log^2(n)/n$. Later, Gaudio and Mossel studied reconstruction from the 1- and 2-neighbourhoods, giving bounds on the values of $p$ for which $G(n,p)$ is reconsructible. For 1-neighbourhoods, this was improved very recently by Huang and Tikhomirov who determined the correct threshold up to logarithmic factors, around $n^{−1/2}$. In this talk we will show new bounds on p for the $r$-reconstructibility problem in $G(n, p)$. We improve the bounds for 2-neighbourhoods given by Gaudio and Mossel by polynomial factors. We also improve the result of Huang and Tikhomirov for 1-neighbourhoods, showing that the logarithmic factor is necessary. Finally, we determine the exact thresholds for $r$-reconstructibility for $r \ge 3$. If time permits, I will also discuss new related results on reconstruction of random directed graphs and random matrices.

  This based on joint works with Tom Johnston, Alexander Roberts, Alex Scott, Paul Balister, and Youri Tamitegama.

  
  

  This talk will be in Bedford Way (20) room 822.