4
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ Since it's undirected, I guess you mean that each $i$ is connected to $i \pm 1$ and $i \pm 2$? $\endgroup$
    – JBL
    Nov 2, 2010 at 3:21
  • $\begingroup$ yes, added clarification $\endgroup$ Nov 2, 2010 at 3:39
  • $\begingroup$ 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. $\endgroup$ Nov 2, 2010 at 8:34
  • $\begingroup$ 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. $\endgroup$ Nov 2, 2010 at 9:11
  • $\begingroup$ I now have a complete proof that $\mu \approx 2.20556943040059$, following the steps of my answer below. $\endgroup$ Nov 7, 2010 at 5:19

1 Answer 1

3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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, ...). $\endgroup$
    – JBL
    Nov 2, 2010 at 12:23
  • 1
    $\begingroup$ Nor should it: I'm disregarding both the initial phase (which has polynomial multiplicative contribution) and some dead-end paths. $\endgroup$ Nov 2, 2010 at 16:32
  • $\begingroup$ 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. $\endgroup$ Nov 2, 2010 at 16:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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