2021/04/12 by Tom Hutchcroft, Hutchcroft, Tom, Matthew Tointon +1
Mathematics · Physics and Astronomy · #Combinatorics (math.CO) #FOS: Mathematics #Group Theory (math.GR) #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Stochastic processes and statistical mechanics #Theoretical and Computational Physics
paper · pdf · doi:10.48550/arxiv.2104.05607
openalex publication_date 2021/04/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We prove that if (Gn)n≥1=((Vn,En))n≥ 1 is a sequence of finite, vertex-transitive graphs with bounded degrees and |Vn|→∞ that is at least (1+ε)-dimensional for some ε>0 in the sense that diam (Gn)=O(|Vn|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 pc(α)<1 such that for each p≥ pc(α), Bernoulli-p bond percolation on Gn has a cluster of size at least α|Vn| 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 (Gn)=O((|Vn|)/((log |Vn|)a)) 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 Gn 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 pu<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 pc=1 or pc≤ 1-ε.