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

Abstract

We prove that if $(G_n{)}_{n\ge 1}=((V_n,E_n){)}_{n\ge 1}$ is a sequence of finite, vertex-transitive graphs with bounded degrees and $|V_n|\to \infty$ that is at least $(1+\epsilon )$-dimensional for some $\epsilon >0$ in the sense that

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<\alpha <1$ there exists $p_c(\alpha )<1$ such that for each $p\ge p_c(\alpha )$, Bernoulli-$p$ bond percolation on $G_n$ has a cluster of size at least $\alpha |V_n|$ with probability tending to $1$ as $n\to \infty$. In fact, we prove more generally that there exists a universal constant $a$ such that the same conclusion holds whenever

This verifies a conjecture of Benjamini (2001) 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. A key step in our argument is a direct proof of our result when the graphs $G_n$ are all Cayley graphs of Abelian groups, in which case we show that one may indeed take $a=1$. This result relies crucially on a new theorem of independent interest stating roughly that balls in arbitrary Abelian Cayley graphs can always be approximated by boxes in ${\mathbb{Z}}^d$ with the standard generating set. Another key step is to adapt the methods of Duminil-Copin, Goswami, Raoufi, Severo, and Yadin [Duke Math. J. 169 (2020)] from infinite graphs to finite graphs. This adaptation also leads to an isoperimetric criterion for infinite graphs to have a non-trivial 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<\infty$ there exists $\epsilon >0$ such that every infinite graph $G$ of degree at most $k$ whose vertex set has at most $n$ orbits under $\mathrm{Aut}(G)$ has either $p_c=1$ or $p_c\le 1-\epsilon$.