Critical threshold for regular graphs

Ishaan Bhadoo

Abstract

In this article, we study the critical percolation threshold $p_{c}$ for $d$ -regular graphs. It is well-known that $p_{c}\geq\frac{1}{d-1}$ for such graphs, with equality holding for the $d$ -regular tree. We prove that among all quasi-transitive $d$ -regular graphs, the equality $p_{c}(G)=\frac{1}{d-1}$ holds if and only if $G$ is a tree. Furthermore, we provide counterexamples that illustrate the necessity of the quasi-transitive assumption.

1 Introduction

Consider independent (Bernoulli) bond¹¹1Although we work with bond percolation, the same methods apply to site percolation. percolation on a locally finite, connected, infinite simple graph $G$ (all graphs are assumed to satisfy these conditions unless stated otherwise), i.e. we retain edges with probability $p$ and throw them away with probability $1-p$ .

We use $\mathbb{P}_{p}$ to denote the corresponding percolation measure. An important function to consider in the context of percolation is, $\psi(p)=\mathbb{P}_{p}(\exists\ \text{an infinite connected component})$ . This leads to the definition of the critical parameter:

p_{c}:=\sup\{p:\psi(p)=0\}

Determining the exact value of $p_{c}$ is challenging for most graphs; however for $d$ -regular trees, one can show that $p_{c}=\frac{1}{d-1}$ . The proof follows two steps: First, by a first-moment argument one can show that a graph $G$ with maximal degree $d<\infty$ satisfies $p_{c}(G)\geq\frac{1}{d-1}.$ Second, for trees with degree $d$ , by a dual second moment upper bound we can get $p_{c}\leq\frac{1}{d-1}$ , implying $p_{c}=\frac{1}{d-1}$ (see [Roc24, Claim 2.3.9] for details).

This leads to the following question: consider percolation on a $d$ -regular graph $G$ , are trees the only graphs with $p_{c}=\frac{1}{d-1}?$

The goal of this article is to show that trees are the only graphs with $p_{c}=\frac{1}{d-1}$ in the space of all $d$ -regular quasi-transitive graphs. We start with some definitions. For a graph $G$ , let $\mathrm{AUT}(G)$ be the group of all automorphisms (adjacency preserving bijections) of $G.$

Definition 1.

A graph $G$ is called quasi-transitive if the number of orbits for the action of $\mathrm{AUT}(G)$ on $G$ is finite. It is called transitive if there is only one orbit

Under the assumption of quasi-transitivity we have the following theorem:

Theorem 2.

Let $G$ be a quasi-transitive $d$ -regular graph. Then $p_{c}(G)\geq\frac{1}{d-1}$ and equality holds if and only if $G$ is a tree.

It is important to note that being quasi-transitive is essential. In Section 2, using the general theory for percolation on trees we give a counterexample (for each $d\geq 3$ ) when one drops this assumption. Next, we show the above theorem by constructing a covering of every quasi-transitive $d$ -regular graph using regular trees and then use the strict monotonicity result of [MS19]. The main tools we use are from [MS19] and [LP17]. For completeness, we cover the required background for percolation on trees and some techniques from the theory of coverings, in an effort to make this article self-contained.

1.1 Connection to the connective constant

A self-avoiding walk is a path that visits no vertex more than once. To define the connective constant, fix a starting vertex $o$ , the set of all self-avoiding walks of length $n$ starting at $o$ is denoted as $\text{SAW}_{n}$ . The connective constant $\mu(G)$ of a graph $G$ is then defined as

\mu(G):=\underset{n\rightarrow\infty}{\lim}|\text{SAW}_{n}|^{\frac{1}{n}}

By Fekete’s lemma, it can be checked that this limit exists. The connective constant is closely related to the critical threshold by the following standard lemma (see [LP17]).

Lemma 3.

For any connected infinite graph $G,\ p_{c}(G)\geq\frac{1}{\mu(G)}.$ ²²2 $\text{This also shows}\ p_{c}(G)\geq\frac{1}{d-1}\text{for a graph with maximum degree}\ d.$

Proof.

Let $\mathcal{C}(o)$ denote the connected component of $o$ in Bernoulli percolation with parameter $p$ . Define $S_{n}(o)$ as the set of self-avoiding walks of length $n$ within $\mathcal{C}(o)$ . If $\mathcal{C}(o)$ is infinite, then $S_{n}(o)\neq\emptyset$ for all $n$ . From this, we deduce:

\mathbb{P}_{p}(o\leftrightarrow\infty)\leq\mathbb{P}_{p}[S_{n}(o)\neq\emptyset]\overset{\text{(Markov's Ineq)}}{\leq}\mathbb{E}_{p}[|S_{n}(o)|]=|\text{SAW}_{n}|p^{n}.

By taking $n$ -th roots we get, $1\leq\mu(G)p\ \text{whenever }\mathbb{P}_{p}(o\leftrightarrow\infty)>0.$ In particular, this holds for $p>p_{c}$ . ∎

An analogous statement to Theorem 2 regarding the connective constant was previously shown by Grimmett and Li [GL15, Thm 4.2].

Theorem 4 (G. Grimmett, Z. Li, [GL15]).

Let $G=(V,E)$ be a $d$ -regular quasi-transitive graph and let $d\geq 3$ . We have that $\mu(G)<d-1$ if $G$ has cycles.

By using Lemma 3, Theorem 2 follows. However, the techniques used in the proof of Theorem 4 are entirely combinatorial and therefore differ from our method.

2 Percolation on trees

In this section for $d\geq 3$ we give an example of a $d$ -regular graph with cycles such that $p_{c}=\frac{1}{d-1}$ (such an example cannot exist for $d=2)$ . To do this we use the theory of percolation on locally finite trees. We start by defining the branching number of a locally finite tree.

2.1 Branching number and the critical point for trees

Suppose $T=(V,E)$ is an infinite locally finite tree with root $O$ . We imagine the tree $T$ as growing downward from the root $O$ . For $x,y\in V$ , we write $x\leq y$ if $x$ is on the shortest path from $O$ to $y$ ; and $T_{x}$ for the subtree of $T$ containing all the vertices $y$ with $y\geq x$ . For a vertex $x\in V$ we denote by $d(x,O)$ the graph distance from $O$ to $x$ . We want to understand the critical point for a tree, motivated by the comparison from Galton-Watson branching processes this naturally leads us to the study of the average number of branches coming out of a vertex which is called the branching number of a tree. To rigorously define this we use conductances and flows on trees. For each edge $e$ we define the conductance of an edge to be $c(e):=\lambda^{-|e|}$ , where $|e|$ denotes the distance of the edge $e$ from the root $O.$ It is natural to define conductances decreasing exponentially with the distance since trees grow exponentially.

If $\lambda$ is very small then due to large conductances there is a non-zero flow on the tree satisfying $0\leq\theta(e)\leq\lambda^{-|e|}$ . While increasing the value of $\lambda$ we observe a critical value $\lambda_{c}$ above which such a flow does not exists. This is precisely the branching number. Specifically,

br(T):=\sup\{\lambda:\exists\ \text{a non-zero flow}\ \theta\ \text{on}\ T\ \text{such that}\ 0\leq\theta(e)\leq\lambda^{-|e|}\ \forall\ e\in T\}

By using the max-flow min-cut theorem we get that,

br(T)=\sup\{\lambda:\inf_{\pi}\displaystyle\sum_{e\in\pi}\lambda^{-|e|}>0\}

Where the infimum is over all cutsets $\pi$ separating $O$ from $\infty.$ Using this as the definition it is easy to see that $p_{c}\geq\frac{1}{br(T)}$ , indeed by using a first moment bound at $\lambda=\frac{1}{p}$ for $p>p_{c}.$ By using a (weighted) second-moment method it can be shown that the reverse inequality also holds. In particular, we have the following result of Lyons.

Theorem 5 (R. Lyons, [Lyo90]).

Let $T$ be a locally finite, infinite tree then, $p_{c}(T)=\frac{1}{br(T)}$ where $br(T)$ is the branching number of the tree.

Proof: The proof essentially uses a lower bound on being connected to infinity in terms of conductances [Lyo92]. See [LP17] for the proof.

Thus, to find the critical threshold for a tree one needs to know how to compute its branching number. However, the definition of the branching number makes this in general hard, thankfully, for sub-periodic trees (defined below) we have a significantly easier method of calculating the branching number.

2.2 Superiodic trees

For a tree $T$ we define its upper exponential growth rate as

\overline{grT}:=\limsup_{n\rightarrow\infty}|T_{n}|^{\frac{1}{n}}

where $T_{n}$ is the number of vertices at a distance $n$ from $O.$ Similarly one can define the lower exponential growth rate as

\underline{grT}:=\liminf_{n\rightarrow\infty}|T_{n}|^{\frac{1}{n}}

We say that the exponential growth rate exists if $\overline{grT}=\underline{grT}$ .

We now recall the definition of subperiodic trees from [LP17]. Fix a $N\geq 0$ . An infinite tree $T$ is called $N$ - subperiodic if $\forall x\in T$ there exists an adjacency preserving injection $f:T_{x}\rightarrow T_{f(x)}$ with $|f(x)|\leq N$ (where $|\cdot|$ is the distance from $O$ ). A tree is called subperiodic if there exists a $N$ for which it is $N$ -subperiodic. Since in general the growth rate is easier to calculate, the following theorem is the key to calculating $p_{c}$ for subperiodic trees.

Theorem 6 (Subperiodicity and Branching Number, [LP17]).

For every subperiodic infinite tree $T$ , the exponential growth rate exists and $\text{br}T=\text{gr}T.$

2.3 Non quasi-transitive counter-examples

Refer to caption — Figure 1: On removing the edge $e$ we get a sub-periodic tree $T$ with gr $T=$ br $T=d-1$

We are now ready to give our counterexamples. Let $T$ be a tree with root $O$ such that every vertex in $T$ has degree $d$ , except two vertices $X$ , $Y$ that are adjacent to the root having degree $d-1$ . Hence, $T=(V,E)$ is the graph formed by all black edges shown in Figure 1. Now define $G:=T\cup\{e\}=(V,E\cup\{e\})$ to be the graph obtained after adding the red edge e. We claim that $p_{c}(G)=\frac{1}{d-1}.$

For the tree $T$ , $|T_{1}|=d$ , $|T_{2}|=(d-2)(d-1)+2(d-2)=(d-2)(d+1)$ , after this point every point has $d-1$ branches coming out, so $|T_{2+n}|=(d-2)(d+1)(d-1)^{n}$ . Therefore $\text{gr}T=d-1.$

$T$ is clearly subperiodic since, for all $x$ such that $d_{T}(x,O)\geq 2$ , we have $T_{x}$ is exactly $T_{A}$ , allowing us to define the function $f(v)=\phi(v)$ , where $\phi$ is the isomorphism between $T_{x}$ and $T_{A}$ . Thus, $T$ is 1-subperiodic. By Theorem 6, $\text{br}T=\text{gr}T=d-1$ . Hence, $p_{c}(T)=\frac{1}{d-1}.$

Since $T$ is a subgraph of $G$ , we have $p_{c}(G)\leq p_{c}(T)=\frac{1}{d-1}$ . However, $G$ is of degree $d$ , so by a standard first-moment bound, $p_{c}(G)\geq\frac{1}{d-1}$ . Combining these two observations, we conclude that $p_{c}(G)=\frac{1}{d-1}$ . Thus, $G$ is a $d$ -regular graph with cycles such that $p_{c}(G)=\frac{1}{d-1}$ . Finally, the fact that $G$ is not quasi-transitive follows from Theorem 2.

3 Proof of the Theorem

We now show that if $G$ is a quasi-transitive, $d$ -regular graph then $p_{c}(G)>\frac{1}{d-1}.$ The key idea is to cover every quasi-transitive $d$ -regular graph (with cycles) by a $d$ -regular tree. We start by defining what a covering map means in the context of percolation, next we use the results of Martineau and Severo [MS19] about critical thresholds under coverings.

3.1 Critical points under coverings

The question of critical points under coverings was asked by Benjamini and Schramm in their celebrated paper “ Percolation beyond $\mathbb{Z}^{d},$ Many Questions and a Few Answers” [BS96, Question 1]. They conjectured that if $G,H$ are quasi-transitive graphs and $G$ covers but is not isomorphic to $H$ and $p_{c}(G)<1$ then $p_{c}(G)<p_{c}(H)$ . This conjecture was resolved by Martineau and Severo [MS19]. Following their paper we set up some definitions necessary to define a covering map.

Consider a map $\pi:V(G)\rightarrow V(H)$ , we say that this map is a strong covering map if its $1$ -Lipscitz (i.e. $d_{H}(\pi(x),\pi(y))\leq d_{G}(x,y)$ ) and it has the strong lifting property: for every $x\in V(G)$ , and for every neighbour $u$ of $\pi(x)$ there is a unique neighbour of $x$ that maps to $u$ . Next we say that a map $\pi:V(G)\rightarrow V(H)$ has uniformly non-trivial fibres ([Sev20]) if there exists $R$ such that for all $x\in V(G)$ there exists $y\in V(G)$ such that $\pi(x)=\pi(y)$ and $0<d_{G}(x,y)\leq R$ . We are now ready to state the main tool:

Theorem 7 (F.Severo, S. Martineau, [MS19]).

Let $G$ and $H$ be graphs of bounded such that there is a map $\pi:V(G)\rightarrow V(H)$ which is a strong covering map with uniformly non-trivial fibres. Then if $p_{c}(G)<1$ , we have $p_{c}(G)<p_{c}(H).$

The above result relies on the theory of enhancements. A technique first introduced by Aizenmann and Grimmett [AG91] as a recipe to prove strict inequalities between critical points of graphs, and is part of a more general idea of interpolation between percolation configurations [Sev20]. For background on the technique of enhancements see [Sev20], [BBR14]. We now show that this holds for $G=d$ -regular tree and $H$ a $d$ -regular quasi-transitive graph with cycles. In particular, we have the following:

Proposition 8.

Let $T_{d}$ be the $d$ -regular tree and $H$ be a quasi-transitive $d$ -regular graph with cycles, then there exists a strong covering map $\pi$ with uniformly non-trivial fibres from $V(T_{d})$ to $V(H).$

Proof.

We start by constructing a graph $X$ from our graph $H$ which covers $H$ and is isomorphic to $T_{d}$ . Fix a vertex $x_{0}\in V(H).$ Define the vertices of $X$ to be the non-backtracking paths $<x_{0},x_{1},\cdots x_{n}>$ starting at $x_{0}$ (a path $<x_{0},x_{1},\cdots x_{n}>$ is called non-backtracking if $x_{i+2}\neq x_{i}\ \forall i$ ). Two paths are connected in $X$ if one is an extension of the other by an edge (this is precisely the universal cover). We claim that for a $d$ -regular $H$ , $X$ is isomorphic to $T_{d}.$

The fact that $X$ is a tree is clear since all paths are non-backtracking and start at a fix vertex $x_{0}.$ Now any point $<x_{0},x_{1},\cdots,x_{n}>$ has neighbours as $<x_{0},x_{1}\cdots,x_{n-1}>$ and $<x_{0},x_{1},\cdots,x_{n},u>$ where $u$ runs over all neighbours of $x_{n}$ not equal to $x_{n-1},$ this shows $d$ -regularity. Therefore $X\cong T_{d}.$

For the covering map we let $\pi$ be the map which projects every path to its last vertex, more formally define $\pi:V(T_{d})\rightarrow V(H)$ such that $\pi(<x_{0},x_{1},\cdots x_{n}>)=x_{n}$ where we identify $T_{d}$ with $X.$ We now show that this is a strong covering map with uniformly non-trivial fibres.

Lipschitz property. Let $x=\ <x_{0},\cdots,x_{n}>,y=\ <y_{0},\cdots,y_{m}>$ . We want to show that $d_{H}(\pi(x),\pi(y))=d_{H}(x_{n},y_{m})\leq d_{X}(x,y)$ . Let $z$ be the common ancestor of $x,y$ in $X$ . Then $d_{X}(x,y)=d_{X}(x,z)+d_{X}(z,y).$ Since $x$ is a descendant of $z$ it is easy to see that $d_{X}(x,z)\geq d_{H}(\pi(x),\pi(z)).$ Thus by the above equation $d_{X}(x,y)\geq d_{H}(\pi(x),\pi(y)).$

Uniformly non-trivial fibres. We show that there are uniformly non-trivial fibres. This is the only property that requires quasi-transitivity. Pick a $x=<x_{0},x_{1},\cdots,x_{n}>$ . By quasi-transitivity, we can find a $K$ (independent of $x_{n}$ ) such that there is a cycle (not necessarily simple) $C=<x_{n},x_{n+1},\cdots,x_{n+m}=x_{n}>$ of length $m\leq K.$ If $x_{n-1}=x_{n+1}$ , then $y=<x_{0},\cdots,x_{n-1},x_{n+2},\cdots x_{n+m}=x>$ is a non-backtracking path satisfying $\pi(x)=\pi(y).$ Otherwise, consider the path $y=<x_{0},x_{1},\cdots,x_{n-1},x_{n},x_{n+1},\cdots,x_{n}>$ since $x_{n-1}\neq x_{n+1}$ , this is a non-backtracking path and gets mapped $\pi(x)$ .

Strong lifting property. Pick a $x=<x_{0},x_{1},\cdots x_{n}>\ \in V(X)$ , for any neighbour $u$ of $\pi(x)$ we need to find a neighbour of $x$ mapping to it. If $u=x_{n-1}$ then let that neighbour be $<x_{0},x_{1},\cdots x_{n-1}>$ , otherwise let it be $<x_{0},x_{1},\cdots x_{n},u>$ .

Thus $\pi$ is a strong covering map with uniformly non-trivial fibres, which shows the proposition. By our earlier comments, this also proves Theorem 2. ∎

4 Concluding remarks

Even though we worked with quasi-transitive graphs, the same proof extends to graphs with bounded local girth. The concept of bounded local girth can be defined as follows: Consider a vertex $x$ , define the girth of $x$ as

L_{x}:=\inf\{l(C):C\ \text{cycle},C\ni x\}

where $l(C)$ is the length of the cycle $C$ . We say that a graph $G$ has bounded local girth if $\underset{x}{\sup}\ L_{x}<\infty.$

The only place where we used quasi-transitivity was to show that our map has uniformly non-trivial fibres. By bounded local girth, the same proof applies, and hence, for any $d$ -regular graph $G$ , we have $p_{c}(G)>\frac{1}{d-1}$ . Therefore, trees minimize $p_{c}$ in the space of all graphs with bounded local girth or no cycles.

A similar question can be asked for the uniqueness threshold $p_{u}$ . Even though a theorem analogous to Theorem 7 has been established for $p_{u}$ (see [MS19]), the same technique cannot be applied since $p_{u}(T)=1$ for a tree $T.$

5 Acknowledgements

I thank Prof. Subhajit Goswami for suggesting the problem and for his guidance and comments throughout the project. This work was done as part of the Visiting Students Research Program (VSRP 2024) at the Tata Institute of Fundamental Research, Mumbai and I thank them for this opportunity.

References

[AG91] Michael Aizenman and Geoffrey Grimmett. Strict monotonicity for critical points in percolation and ferromagnetic models. Journal of Statistical Physics, 63:817–835, 1991.
[BBR14] Paul Balister, Béla Bollobás, and Oliver Riordan. Essential enhancements revisited. arXiv preprint arXiv:1402.0834, 2014.
[BS96] Itai Benjamini and Oded Schramm. Percolation beyond $\mathbb{Z}^{d}$ , many questions and a few answers. 1996.
[GL15] Geoffrey R Grimmett and Zhongyang Li. Bounds on connective constants of regular graphs. Combinatorica, 35(3):279–294, 2015.
[LP17] Russell Lyons and Yuval Peres. Probability on trees and networks, volume 42. Cambridge University Press, 2017.
[Lyo90] Russell Lyons. Random walks and percolation on trees. The Annals of Probability, 18(3):931–958, 1990.
[Lyo92] Russell Lyons. Random walks, capacity and percolation on trees. The Annals of Probability, pages 2043–2088, 1992.
[MS19] Sébastien Martineau and Franco Severo. Strict monotonicity of percolation thresholds under covering maps. 2019.
[Roc24] Sebastien Roch. Modern discrete probability: An essential toolkit. Cambridge University Press, 2024.
[Sev20] Franco Severo. Interpolation schemes in percolation theory. PhD thesis, Université Paris-Saclay; Université de Genève, 2020.

Ishaan Bhadoo, DPMMS, University of Cambridge, UK.
Email address: [email protected]