I am interested in long-range percolation models with heavy-tailed degree distributions such as DHH13, GLM21, Y6. The simplest example is scale-free percolation in which vertices are elements $\mathbb{Z}^d$, each vertex $x\in\mathbb{Z}^d$ carries and independent random heavy-tailed weight $W_x>0$ and two vertices $x,y$ are joined by an edge with probability $1-\exp(W_xW_y/|x-y|^\alpha), \alpha>d$, independently (given the weights). If $W_x$ has a first moment but no second moment, then the model is "robust" under Bernoulli percolation, in the sense that almost surely $p_c^{\text{bond}}=p_c^{\text{site}}=0$ for the random graph produced.
Some recent results are concerned with the question of recurrence and transience of simple random walk on the infinite clusters in these percolation models. Specifically, it was shown in HH17, GHMM19 that robust infinite clusters are transient almost surely. The proofs are constructive but quite model specific and are based on a strategy from B2 designed for long-range percolation without weights; they do not use robustness directly in an essential way.
My feeling is that the robustness property (in particular the "site version" $p_c^{\text{site}}=0$) is so strong (for example it implies super-exponential growth) that it should imply transience for a much larger class of infinite random graphs than these rather specific models, for instance unimodular random measures concentrated on robust infinite graphs.
In the case of random trees, $p_c^{\text{bond}}=0$ clearly implies transience but I have so far not found any results in that direction concerning non-tree like graphs.
My questions are:
- Are there any results in the literature that shed light on the structure of random graphs with finite mean degree under the assumption $p_c=0$ or maybe other "extreme" assumptions on growth or isoperimetry?
- Is there an example of a (not necessarily random) graph with $p_c^{\text{site}}=0$ that is recurrent?
Best Answer
I will first construct a simple deterministic example of a recurrent graph with $p_c^\mathrm{site}=0$ and then show how it can be modified to be a unimodular random rooted graph (see e.g. Nicolas Curien's lecture notes for the definition https://drive.google.com/file/d/16qEMGJU2g01g4YWkYtVKTSqetk-SpRmy/view)
Suppose we take a half-infinite line indexed by $\mathbb{N}=\{1,2,3,\ldots\}$ and, for each $n$, replace the vertex labelled $n$ with a complete graph of size $f(n)$ for some function $f:\mathbb{N}\to\mathbb{N}$ to be chosen later, where every vertex in the $n$th complete graph is connected to every vertex in the adjacent complete graphs at $n$ and $n-1$. In this example, site percolation occurs if there is at least one open vertex in the complete graph at $n$ for every sufficiently large $n$. From this and Borel-Cantelli, we see that $p_c^\mathrm{site}<1$ when $f(n)=\Omega(\log n)$ and $p_c^\mathrm{site}=0$ when $f(n)=\omega(\log n)$. If we take, say, $f(n)=\lceil(\log (n+2))\rceil^2$ then the resulting graph therefore has $p_c^\mathrm{site}=0$ but is recurrent by the Nash-Williams criterion since there are $O((\log n)^4)$ edges between the $n$th and $(n+1)$th complete graphs and $\sum_{n=2} (\log n)^{-4}=\infty$. (Note in particular that we have a lot of room in this construction!)
We can make something similar work as a unimodular random rooted graph by using the canopy trees instead of the half-infinite line. This is a pretty standard trick, you can see lots of instances of it in this paper of Omer Angel and myself https://arxiv.org/abs/1710.03003
Indeed, if we take the canopy tree and replace each vertex at height $n$ with a complete graph of size $\lceil (\log (n+2))\rceil^2$ then the resulting graph is recurrent but has $p_c^\mathrm{site}=0$ for similar reasons to the line example. Since the probability that the root of the canopy tree is at height $n$ is $2^{-n}$, we can make this graph unimodular by biasing the height of the root vertex of the canopy tree by $\lceil (\log (n+2))\rceil^2$ then choosing uniformly one of the vertices of the complete graph at that vertex as the root of the new graph (this biasing makes sense since $\lceil (\log (X+2))\rceil^2$ is integrable when $X$ is a geometric random variable). Note that this graph also has rather light tailed degrees: The probability that the root has degree at least $n$ is roughly of order $2^{-\Theta(e^{\sqrt{n})}$.
Basically these examples work because replacing edges by parallel edges (or blowing up vertices into complete graphs) has a much stronger effect on percolation than it does on the random walk.