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 3neighbourhoods with high probability provided that $p \gg \log^2(n)/n$. Later, Gaudio and Mossel studied reconstruction from the 1 and 2neighbourhoods, giving bounds on the values of $p$ for which $G(n,p)$ is reconsructible. For 1neighbourhoods, 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 2neighbourhoods given by Gaudio and Mossel by polynomial factors. We also improve the result of Huang and Tikhomirov for 1neighbourhoods, 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.