TY - JOUR

T1 - Noise sensitivity of critical random graphs

AU - Lubetzky, Eyal

AU - Peled, Yuval

N1 - Funding Information:
E.L. was supported in part by NSF grant DMS-1812095.
Publisher Copyright:
© 2022, The Hebrew University of Jerusalem.

PY - 2022

Y1 - 2022

N2 - We study noise sensitivity of properties of the largest components (Cj)j≥1 of the random graph G(n,p) in its critical window p = (1+λn−1/3)/n. For instance, is the property “|C1| exceeds its median size” noise sensitive? Roberts and Şengül (2018) proved that the answer to this is yes if the noise ε is such that ε ≫ n−1/6, and conjectured the correct threshold is ε ≫ n−1/3. That is, the threshold for sensitivity should coincide with the critical window—as shown for the existence of long cycles by the first author and Steif (2015). We prove that for ε ≫ n−1/3 the pair of vectors n-1/3Cj)j≥1 before and after the noise converges in distribution to a pair of i.i.d. random variables, whereas for ε ≪ n−1/3 the ℓ2-distance between the two goes to 0 in probability. This confirms the above conjecture: any Boolean function of the vector of rescaled component sizes is sensitive in the former case and stable in the latter. We also look at the effect of the noise on the metric space n-1/3Cj)j≥1. E.g., for ε ≥ n−1/3+o(1), we show that the joint law of the spaces before and after the noise converges to a product measure, implying noise sensitivity of any property seen in the limit, e.g., “the diameter of C1 exceeds its median.”

AB - We study noise sensitivity of properties of the largest components (Cj)j≥1 of the random graph G(n,p) in its critical window p = (1+λn−1/3)/n. For instance, is the property “|C1| exceeds its median size” noise sensitive? Roberts and Şengül (2018) proved that the answer to this is yes if the noise ε is such that ε ≫ n−1/6, and conjectured the correct threshold is ε ≫ n−1/3. That is, the threshold for sensitivity should coincide with the critical window—as shown for the existence of long cycles by the first author and Steif (2015). We prove that for ε ≫ n−1/3 the pair of vectors n-1/3Cj)j≥1 before and after the noise converges in distribution to a pair of i.i.d. random variables, whereas for ε ≪ n−1/3 the ℓ2-distance between the two goes to 0 in probability. This confirms the above conjecture: any Boolean function of the vector of rescaled component sizes is sensitive in the former case and stable in the latter. We also look at the effect of the noise on the metric space n-1/3Cj)j≥1. E.g., for ε ≥ n−1/3+o(1), we show that the joint law of the spaces before and after the noise converges to a product measure, implying noise sensitivity of any property seen in the limit, e.g., “the diameter of C1 exceeds its median.”

UR - http://www.scopus.com/inward/record.url?scp=85139412081&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85139412081&partnerID=8YFLogxK

U2 - 10.1007/s11856-022-2354-y

DO - 10.1007/s11856-022-2354-y

M3 - Article

AN - SCOPUS:85139412081

JO - Israel Journal of Mathematics

JF - Israel Journal of Mathematics

SN - 0021-2172

ER -