Characterizations of amenability through stochastic domination and finitary codings

We establish new characterizations of amenability of graphs through two probabilistic notions: stochastic domination and finitary codings (also called finitary factors). On the stochastic domination side, we show that the plus state of the Ising model at very low temperature stochastically dominates a high density Bernoulli percolation if and only if the underlying graph is nonamenable. This answers a question of Liggett and Steif [Ann. Inst. H. Poincaré Probab. Statist. 42 (2006), pp. 223–243]. We prove a similar result for the “infinite cluster process” of Bernoulli percolation, where a site is open if it belongs to an infinite open cluster of the underlying Bernoulli percolation. This is of particular interest as this process is not monotone and does not possess any nice form of the domain Markov property. We also prove that the plus states of the Ising model at very low temperatures are stochastically ordered if and only if the graph is nonamenable. This answers a second question of Liggett and Steif. We further show that these stochastic domination results can be witnessed by invariant monotone couplings. On the finitary coding side, we show that the plus state of the Ising model at very low temperature is a finitary factor of an i.i.d. process if and only if the underlying graph is nonamenable (assuming it supports a phase transition). We show a similar result for the infinite cluster process of a high-density Bernoulli percolation, with the assumption that p u > 1 p_u>1 when the graph is one-ended. A main technique is to dilute the processes using independent Bernoulli percolation, which allows us to establish a version of the so-called Holley condition for the diluted processes. We also apply a more complicated dilution mechanism using lattice gas theory in order to stochastically compare two Ising models. Along the way we develop general tools to establish invariant domination in infinite graphs when Holley’s condition is satisfied. The finitary factor results are based on the stochastic domination results and a dynamical construction involving bounding chains, along with a new technique to analyze coupling from the past in infinite-range processes via a novel disease spreading model, which we believe is of independent interest.