{
  "id": "2104.05607",
  "version": "v1",
  "published": "2021-04-12T16:27:10.000Z",
  "updated": "2021-04-12T16:27:10.000Z",
  "title": "Non-triviality of the phase transition for percolation on finite transitive graphs",
  "authors": [
    "Tom Hutchcroft",
    "Matthew Tointon"
  ],
  "comment": "60 pages",
  "categories": [
    "math.PR",
    "math.CO",
    "math.GR"
  ],
  "abstract": "We prove that if $(G_n)_{n\\geq1}=((V_n,E_n))_{n\\geq 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 \\[\\mathrm{diam} (G_n)=O\\left(|V_n|^{1/(1+\\epsilon)}\\right) \\text{ as $n\\to\\infty$}\\] 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\\geq 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 \\[\\mathrm{diam} (G_n)=O\\left(\\frac{|V_n|}{(\\log |V_n|)^a}\\right) \\text{ as $n\\to\\infty$.}\\] 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<\\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 Aut$(G)$ either has $p_c=1$ or $p_c\\leq 1-\\epsilon$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-04-12T16:27:10.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "finite transitive graphs",
      "infinite graph",
      "non-triviality",
      "nontrivial uniqueness phase",
      "bernoulli bond percolation"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 60,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}