Talk information

Date: Sunday, November 24, 2024
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Yuval Peled (Hebrew University)
Title: Noise sensitivity of critical random graphs and the MST

Abstract:

The largest components $C_1,C_2,C_3,…$ of a $G(n,p)$ random graph in the critical window $p=(1+\lambda n^{−1/3})/n$ are known to converge, in several concrete meanings, to a non-trivial random scaling limit. For example, the size of the largest component divided by $n^{2/3}$ converges in distribution to a continuous random variable that was famously identified by Aldous in the 90’s.

In this talk we will study the sensitivity of the limiting properties of these components under a noise operator that resamples every edge independently with probability $\epsilon$. For example, we ask: for which values of $\epsilon$ are the properties “$|C_1|$ exceeds $2*n^{2/3}$” or “the diameter of $C_2$ is smaller than its median” noise-sensitive?

Our main finding is a dichotomy for noise sensitivity that coincides with the critical window: If the noise parameter $\epsilon \gg n^{−1/3}$ then such properties are noise-sensitive, while for $\epsilon \ll n^{−1/3}$ they are noise-stable.

If time permits, we will also present the very same dichotomy for the noise-sensitivity of metric properties of the random Minimum Spanning Tree of the complete $n$-vertex graph.

Based on joint works with Eyal Lubetzky and Omer Israeli.