A Caltech Library Service

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

Hutchcroft, Tom and Tointon, Matthew (2021) Non-triviality of the phase transition for percolation on finite transitive graphs. . (Unpublished)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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 - ϵ.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Hutchcroft, Tom0000-0003-0061-593X
Tointon, Matthew0000-0001-8086-9280
Additional Information:The first author was supported in part by ERC starting grant 804166 (SPRS) and thanks Gabor Pete for helpful discussions. The second author was partially supported by the Stokes Research Fellowship at Pembroke College, Cambridge. He is also grateful to Itai Benjamini and Ariel Yadin for introducing him to the problems considered in this paper, and to Romain Tessera for helpful conversations.
Funding AgencyGrant Number
European Research Council (ERC)804166
Pembroke College, CambridgeUNSPECIFIED
Record Number:CaltechAUTHORS:20210924-202143857
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:111039
Deposited By: George Porter
Deposited On:27 Sep 2021 15:17
Last Modified:27 Sep 2021 15:17

Repository Staff Only: item control page