Expected number of self-avoiding walks of a given length in a random graph

Question

Let us consider the following random locally finite (i.e., every vertex has a finite degree) graph:

$\mathbb{Z}^d$ ($d\geq2$) is the set of vertices and any two vertices $v$ and $w$ have an edge between them with the probability $1-e^{-\beta||v-w||^{-1}}$, where $\beta$ is a fixed constant, and $||\cdot||$ is the metric distance. This is basically the model discussed by Duminil-Copin and Tassion in this work. One has to keep in mind that the model is locally finite, so any vertex can admit only finitely many edges attached to it.

Let $N_{v,n}$ be the number of self-avoiding paths of length (graph-distance) $n$, starting from $v\in\mathbb{Z}^d$. I am trying to compute the expectation $\mathbb{E}(N_{0,n})$. My guesses are, it should be of the form $C^n$ for some $C>0$, but I've not been able to prove this yet. Any help is much appreciated.

Answer 1

I would think the standard proof of Hammersley and Morton would work. You should be able to prove that the $\mathbb{E}(N_{0,n})$ sequence is submultiplicative, leading to the existence of a connective constant, and proving that it is >0 with a counting argument.

You can follow along this article from Tom Hutchcroft : https://arxiv.org/pdf/1708.09460.pdf

Answer 2

A coarse bound, but better than nothing: if $\langle d\rangle$ is the expected degree of a vertex, then the number of self-avoiding walks of length $n$ is between $(\langle d\rangle/2)^n$ and $\langle d\rangle^n$. If $p(\mathbf u)$ denotes the probability of going from a point $\mathbf v$ to $\mathbf u + \mathbf v$, then $$\langle d\rangle = \sum_{\mathbf u \ne \mathbf 0} p(\mathbf u).$$ I will not simplify it because (1) I'm not sure it has a closed form for your probability, and (2) I'm not sure your probability makes sense as stated. But this method works for any translation-invariant set of probabilities.

For the upper bound: if we take the $n^{\text{th}}$ power of the sum above and expand it, we get a sum of all possible terms $p(\mathbf u_1) p(\mathbf u_2) \cdots p(\mathbf u_n)$. When the walk $\mathbf 0$ to $\mathbf u_1$ to $\mathbf u_1 + \mathbf u_2$ to ... to $\mathbf u_1 + \dots + \mathbf u_n$ is a self-avoiding walk, this term is the probability of that walk. Therefore we've summed the probability of all self-avoiding walks. This would give their expected number if we summed nothing else, but our sum also has terms for walks that aren't self-avoiding (those terms may not even be correct probabilities). So $\langle d \rangle^n$ is only an upper bound.

For the lower bound, define $\mathbf u \prec \mathbf v$ if $\mathbf u$ comes before $\mathbf v$ in dictionary order. (That is, if we compare the coordinates of $\mathbf u$ and $\mathbf v$ in order, then $u_i < v_i$ at the first place they differ.) We have $$ \langle d\rangle/2 = \sum_{\mathbf u \succ \mathbf 0} p(\mathbf u). $$ If we take the $n^{\text{th}}$ power of this sum and distribute, we get a sum of all possible terms $p(\mathbf u_1) p(\mathbf u_2) \cdots p(\mathbf u_n)$ where $\mathbf u_1, \dots, \mathbf u_n \succ 0$. Here, the walk $\mathbf 0$ to $\mathbf u_1$ to $\mathbf u_1 + \mathbf u_2$ to ... to $\mathbf u_1 + \dots + \mathbf u_n$ is always a self-avoiding walk: every point comes after all the previous ones in dictionary order. So we get the correct probability of all such self-avoiding walks (and no terms for walks that aren't self-avoiding). However, we don't get all self-avoiding walks, so $(\langle d\rangle/2)^n$ is only a lower bound.