Strong noise sensitivity and random graphs (Q5962538)

The notion of noise sensitivity captures the phenomenon that the value of a Boolean function of many i.i.d. variables can change under small perturbations of its input. It corresponds to the case where a small perturbation of the input variables via i.i.d. noise suffices to make the new value of the function asymptotically independent of its original value. The authors use this concept in selected problems of random graph theory. This paper is divided into five sections. After the introduction, that presents the problem background, the authors give prerequisites on noise sensitivity in Section 2. After this, in Section 3, they present strong noise sensitivity with proofs given for Theorems 1.3 and 1.4. Section 4 presents the dependencies between witnesses for a sufficient condition for strong noise sensitivity. The obtained results are applied in the context of containing a given graph in \(\mathcal{G}(n,p)\) (the Erdős-Rényi random graph). The last section compares the 0-strong and 1-strong noise sensitivity of a function, as well as the validity of these properties under varying levels of noise.