Jeffrey E. Steif

The present text provides the lecture notes for the course "noise sensitivity and percolation" given at the 2010 Clay Summer School in Buzios, Brazil.

Recently the study of noise sensitivity and noise stability of Boolean functions has received considerable attention. The purpose of this paper is to extend these notions in a natural way to a different class of perturbations, namely those arising from running the symmetric exclusion process for a short amount of time. In this study, the case of monotone Boolean functions will turn out to be of particular interest. We show that for this class of functions, ordinary noise sensitivity and noise sensitivity with respect to the complete graph exclusion process are equivalent. We also show this equivalence with respect to stability. After obtaining these fairly general results, we study "exclusion sensitivity" of critical percolation in more detail with respect to medium-range dynamics. The exclusion dynamics, due to its conservative nature, is in some sense more physical than the classical i.i.d dynamics. Interestingly, we will see that in order to obtain a precise understanding of the exclusion sensitivity of percolation, we will need to describe how typical spectral sets of percolation diffuse under the underlying exclusion process.

We show that for any Cayley graph, the probability (at any p ) that the cluster of the origin has size n decays at a well-defined exponential rate (possibly 0). For general graphs, we relate this rate being positive in the supercritical regime with the amenability/nonamenability of the underlying graph.

We show that for any Cayley graph, the probability (at any $p$) that the cluster of the origin has size n decays at a well-defined exponential rate (possibly 0). For general graphs, we relate this rate being positive in the supercritical regime with the amenability/nonamenability of the underlying graph.

In dynamical percolation, the status of every bond is refreshed according to an independent Poisson clock. For graphs which do not percolate at criticality, the dynamical sensitivity of this property was analyzed extensively in the last decade. Here we focus on graphs which percolate at criticality, and investigate the dynamical sensitivity of the infinite cluster. We first give two examples of bounded degree graphs, one which percolates for all times at criticality and one which has exceptional times of nonpercolation. We then make a nearly complete analysis of this question for spherically symmetric trees with spherically symmetric edge probabilities bounded away from 0 and 1. One interesting regime occurs when the expected number of vertices at the nth level that connect to the root at a fixed time is of order n(\log n)^\alpha. R. Lyons (1990) showed that at a fixed time, there is an infinite cluster a.s. if and only if \alpha >1. We prove that the probability that there is an infinite cluster at all times is 1 if \alpha > 2, while this probability is 0 if 1<\alpha \le 2. Within the regime where a.s. there is an infinite cluster at all times, there is yet another type of ``phase transition'' in the behavior of the process: if the expected number of vertices at the nth level connecting to the root at a fixed time is of order n^\theta with \theta > 2, then the number of connected components of the set of times in [0,1] at which the root does not percolate is finite a.s., while if 1<\theta < 2, then the number of such components is infinite with positive probability.

One goal of this paper is to prove that dynamical critical site percolation on the planar triangular lattice has exceptional times at which percolation occurs. In doing so, new quantitative noise sensitivity results for percolation are obtained. The latter is based on a novel method for controlling the "level k" Fourier coefficients via the construction of a randomized algorithm which looks at random bits, outputs the value of a particular function but looks at any fixed input bit with low probability. We also obtain upper and lower bounds on the Hausdorff dimension of the set of percolating times. We then study the problem of exceptional times for certain "k-arm" events on wedges and cones. As a corollary of this analysis, we prove, among other things, that there are no times at which there are two infinite "white" clusters, obtain an upper bound on the Hausdorff dimension of the set of times at which there are both an infinite white cluster and an infinite black cluster and prove that for dynamical critical bond percolation on the square grid there are no exceptional times at which three disjoint infinite clusters are present.

We obtain new results concerning poisoning/nonpoisoning in a catalytic model which has previously been introduced and studied. We show that poisoning can occur even when the arrival rate of one gas is smaller than the sum of the arrival rates of the other gases, and that poisoning does not occur when all gases have equal arrival rates.