Non-triviality of the phase transition for percolation on finite transitive graphs

Abstract

We prove that if (G_n)_(n ≥ 1) = ((V_n,E_n))_(n ≥ 1) is a sequence of finite, vertex-transitive graphs with bounded degrees and |V_n|→∞ that is at least (1+ϵ)-dimensional for some ϵ > 0 in the sense that diam(G_n)=O(|V_n|^(1/(1+ϵ) as n → ∞ then this sequence of graphs has a non-trivial phase transition for Bernoulli bond percolation. More precisely, we prove under these conditions that for each 0<α<1 there exists p_c(α) < 1 such that for each p ≥ p_c(α), Bernoulli-p bond percolation on G_n has a cluster of size at least α|V_n| with probability tending to 1 as n → ∞. In fact, we prove more generally that there exists a universal constant a such that the same conclusion holds whenever diam(G_n) = 0(|V_n|/(log|V_n|α) as n → ∞. This verifies a conjecture of Benjamini up to the value of the constant a, which he suggested should be 1. We also prove a generalization of this result to quasitransitive graph sequences with a bounded number of vertex orbits and prove that one may indeed take a = 1 when the graphs G_n are all Cayley graphs of Abelian groups. A key step in our proof is to adapt the methods of Duminil-Copin, Goswami, Raoufi, Severo, and Yadin from infinite graphs to finite graphs. This adaptation also leads to an isoperimetric criterion for infinite graphs to have a nontrivial uniqueness phase (i.e., to have p_u < 1) which is of independent interest. We also prove that the set of possible values of the critical probability of an infinite quasitransitive graph has a gap at 1 in the sense that for every k,n < ∞ there exists ϵ > 0 such that every infinite graph G of degree at most k whose vertex set has at most n orbits under Aut(G) either has p_c = 1 or p_c ≤ 1 - ϵ.

Files

Additional details