Lectures On Noise Sensitivity And Percolation

Lectures on noise sensitivity and percolation arXiv:1102.5761v1 [math.PR] 28 Feb 2011 Christophe Garban1 1 2 ENS Lyon, CNRS Chalmers University Jeffrey E. Steif2 Contents Overview I 5 Boolean functions and key concepts 1 Boolean functions . . . . . . . . . . . . . . . . . . . . . . . . 2 Some Examples . . . . . . . . . . . . . . . . . . . . . . . . . 3 Pivotality and Influence . . . . . . . . . . . . . . . . . . . . 4 The Kahn, Kalai, Linial Theorem . . . . . . . . . . . . . . . 5 Noise sensitivity and noise stability . . . . . . . . . . . . . . 6 Benjamini, Kalai and Schramm noise sensitivity Theorem . . 7 Percolation crossings: our final and most important example II Percolation in a nutshell 1 The model . . . . . . . . . . . . . 2 Russo-Seymour-Welsh . . . . . . 3 Phase transition . . . . . . . . . . 4 Conformal invariance at criticality 5 Critical exponents . . . . . . . . . 6 Quasi-multiplicativity . . . . . . . III 1 2 3 4 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . and SLE processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Sharp thresholds and the critical point Monotone functions and the Margulis-Russo formula . . KKL away from the uniform measure case . . . . . . . . Sharp thresholds in general : the Friedgut-Kalai Theorem The critical point for percolation for Z2 and T is 12 . . . . Further discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . IV Fourier analysis of Boolean functions 1 Discrete Fourier analysis and the energy spectrum . . . . . . . 2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Noise sensitivity and stability in terms of the energy spectrum 4 Link between the spectrum and influence . . . . . . . . . . . . 5 Monotone functions and their spectrum . . . . . . . . . . . . . 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 9 9 11 12 14 14 16 . . . . . . 21 21 22 23 23 25 26 . . . . . 27 27 28 28 29 30 . . . . . 33 33 34 35 36 37 2 CONTENTS V Hypercontractivity and its applications 1 Heuristics of proofs . . . . . . . . . . . . 2 About hypercontractivity . . . . . . . . . 3 Proof of the KKL Theorems . . . . . . . 4 KKL away from the uniform measure . . 5 The noise sensitivity theorem . . . . . . . . . . . 41 41 42 44 47 49 Appendix on Bonami-Gross-Beckner 1 Tensorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 The one-dimensional case (n = 1) . . . . . . . . . . . . . . . . . . . . . 51 51 52 VI First evidence of noise sensitivity of percolation 1 Influences of crossing events . . . . . . . . . . . . . 2 The case of Z2 percolation . . . . . . . . . . . . . . 3 Some other consequences of our study of influences 4 Quantitative noise sensitivity . . . . . . . . . . . . . . . . 57 57 61 64 66 . . . . . 73 73 75 75 78 78 . . . . . . 83 83 83 87 89 91 92 spectral sample Definition of the spectral sample . . . . . . . . . . . . . . . . . . . . . . A way to sample the spectral sample in a sub-domain . . . . . . . . . . Nontrivial spectrum near the upper bound for percolation . . . . . . . 97 97 99 101 . . . . . . . . . . VII Anomalous fluctuations