E-Book Content
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