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?

Improve this question
$\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
    Commented Nov 2, 2010 at 3:21
  • $\begingroup$ yes, added clarification $\endgroup$
    – Yaroslav Bulatov
    Commented 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$
    – Yuval Filmus
    Commented 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$
    – Yuval Filmus
    Commented 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$
    – Yuval Filmus
    Commented Nov 7, 2010 at 5:19

1 Answer 1

Reset to default
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$.

Improve this answer
$\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
    Commented 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$
    – Yuval Filmus
    Commented 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$
    – Yuval Filmus
    Commented Nov 2, 2010 at 16:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .