Connective constant for self-avoiding walks on a skip-chain

2010-11-02T02:04:21Z

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 by Yuval Filmus for Connective constant for self-avoiding walks on a skip-chain

2010-11-02T09:36:21Z

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:

Hop left $n$ times and get stuck.
Step right to reach $E_0$.
Hop right, step left, hop right, reaching $E_0$.
Hop $m\geq 1$ times right, then step right, reaching $E_m$.
Hop $m\geq 2$ times right, step left, hop $m-1$ times left and get stuck.
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:

Step right.
Hop right, step left, hop right.
Hop $m \geq 1$ times right, step right.
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$.

Connective constant for self-avoiding walks on a skip-chain - MathOverflow

Connective constant for self-avoiding walks on a skip-chain

Answer by Yuval Filmus for Connective constant for self-avoiding walks on a skip-chain