MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Since it's undirected, I guess you mean that each $i$ is connected to $i \pm 1$ and $i \pm 2$? – JBL Nov 2 '10 at 3:21
yes, added clarification – Yaroslav Bulatov Nov 2 '10 at 3:39
I got a recurrence relation for the number of such walks. The first few numbers are 4, 12, 30, 70, 160, 360, 802, 1778, 3932, 8684, 19166, 42286, 93280, 205752, 453818. With some perseverance, one could extract the asymptotics (perhaps even a closed form) from the recurrence relation, but it's a bit messy. – Yuval Filmus Nov 2 '10 at 8:34
Approximately, the process divides into "bricks" of sizes 1,2, and for $n\geq 3$, two bricks of size $n$. The generating series is then $(1-x)/(1-2x-x^3)$. The only real root of the denominator is 0.453397651516404, so your $\mu$ is approximately 2.20556943040059. – Yuval Filmus Nov 2 '10 at 9:11
I now have a complete proof that $\mu \approx 2.20556943040059$, following the steps of my answer below. – Yuval Filmus Nov 7 '10 at 5:19

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$.

share|cite|improve this answer
Yuval, that gives the sequence 1, 1, 2, 5, 11, 24, 53, ..., and this definitely does not match the sequence in question (which, as you note, should begin 1, 4, 12, 30, ...). – JBL Nov 2 '10 at 12:23
Nor should it: I'm disregarding both the initial phase (which has polynomial multiplicative contribution) and some dead-end paths. – Yuval Filmus Nov 2 '10 at 16:32
I should mention that both the initial list (of 6 "ways") and the enumeration of the initial phase was compared against a brute-force enumeration of self-avoiding paths, so I expect it to be correct. It was also derived not in the haphazard way it may look like now. – Yuval Filmus Nov 2 '10 at 16:33

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.