Question

Suppose we have an undirected graph with integer valued nodes where $0<|i-j|\le 2$ implies nodes $i$ and $j$ are connected. Let $c_n$ be the number of self-avoiding walks on this graph of length $n$ starting at origin. Define the connective constant as

$$\mu = \lim_{n\to \infty} c_n^{\frac{1}{n}}$$

What is known about $\mu$? This quantity seems to be related to the transition temperature of an Ising model on such graph, has such model been studied?

Answer 1

A step is a movement of magnitude 1, a hop of magnitude 2.

Denote by $X$ a visited place, by $O$ a place not visited, and by $Y$ the current position. A self-avoiding walk hovers around the states $E_n$, in which the relevant part of the integer line is $X(XO)^nXY$. From this state, the walk can proceed as follows:

1. Hop left $n$ times and get stuck.
2. Step right to reach $E_0$.
3. Hop right, step left, hop right, reaching $E_0$.
4. Hop $m\geq 1$ times right, then step right, reaching $E_m$.
5. Hop $m\geq 2$ times right, step left, hop $m-1$ times left and get stuck.
6. Hop $m\geq 2$ times right, step left, then hop right, reaching $E_0$.

Options 1,5, where the walk gets stuck, seem not to affect the asymptotics (handwaving). Since option 1 is the only one where $n$ (the subscript of $E_n$) matters, we can disregard the subscripts, and just call it $E$.

So we get from $E$ to $E$ by one of the following:

1. Step right.
2. Hop right, step left, hop right.
3. Hop $m \geq 1$ times right, step right.
4. Hop $m \geq 2$ times right, step left, hop right.

In terms of number of steps, these are $1;3;2,3,4,\ldots;4,5,6,\ldots$. In total, we have "bricks" of sizes $1,2$, and two bricks each of sizes $3,4,\ldots$. The corresponding generating series is

$1/(1-x-x^2-2x^3/(1-x)) = (1-x)/(1-2x-x^3)$

The denominator has one real root, about 0.453397651516404. So the $k$ term is $O(2.20556943040059^k)$.

A walk of length $\ell$ reaches state $E$ after one of $O(\ell^2)$ prefixes, some of which are short. So up to a polynomial, the number of walks is the same as the number of walks starting with $E$. Thus $\mu = 2.20556943040059$.