论文标题
关键随机图的噪声灵敏度
Noise sensitivity of critical random graphs
论文作者
论文摘要
我们研究了最大组件的属性的噪声灵敏度$（{\ cal c} _j）_ {j \ geq 1} $在其关键窗口中的随机图$ {\ cal g}（n，p）$的$ p =（1+λn^{ - 1/3}）/n $。例如，属性“ $ | {\ cal c} _1 | $超过其中位数”噪声敏感？ Roberts and}Gengül（2018）证明，如果噪声$ε$是$ε\ gg n^{ - 1/6} $，则答案是肯定的，并指出了正确的阈值是$ε\ gg gg n^{ - 1/3} $。也就是说，灵敏度的阈值应与关键窗口相吻合 - 如第一作者和Steif（2015）的长期周期所示。 我们证明，对于$ε\ gg n^{ - 1/3} $，一对矢量$ n^{ - 2/3}（| {\ cal c} _J |）_ {j \ geq 1} $，前后分配中的噪声收敛到一对i.i.d.d.d.d.d.d.d.d.随机变量，而对于$ε\ ll n^{ - 1/3} $ $ \ ell^2 $ - 两者之间的距离为0，概率为0。这证实了上述猜想：在前一种情况下，重新制定成分大小的矢量的任何布尔函数都是敏感的，在后者中稳定。 我们还查看噪声对度量空间的效果$ n^{ - 1/3}（{\ cal c} _J）_ {j \ geq 1} $。例如，对于$ε\ geq n^{ - 1/3+o（1）} $，我们表明噪声之前和之后的空间的联合定律会收敛到产品度量，这意味着限制中任何属性的噪声敏感性，例如，“ $ {\ cal c} _1 _1 $超过了其中的直径。”
We study noise sensitivity of properties of the largest components $({\cal C}_j)_{j\geq 1}$ of the random graph ${\cal G}(n,p)$ in its critical window $p=(1+λn^{-1/3})/n$. For instance, is the property "$|{\cal C}_1|$ 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 $ε\gg n^{-1/6}$, and conjectured the correct threshold is $ε\gg 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 $ε\gg n^{-1/3}$ the pair of vectors $ n^{-2/3}(|{\cal C}_j|)_{j\geq 1}$ before and after the noise converges in distribution to a pair of i.i.d. random variables, whereas for $ε\ll n^{-1/3}$ the $\ell^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/3}({\cal C}_j)_{j\geq 1}$. E.g., for $ε\geq 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 ${\cal C}_1$ exceeds its median."
