Let $c_n$ be the number of self-avoiding walks in ${\mathbb Z}^2$ of length $n$. Because $c_n$ is a submultiplcative sequence ($c_{n+m} \leq c_nc_m$ for all $n, m \geq 1$), Fekete's lemma tells us that $\lim_{n \rightarrow \infty} c_n^{1/n}$ exists and equals $\inf c_n^{1/n}$. So we can define the connective constant $\mu = \lim_{n \rightarrow \infty} c_n^{1/n}$ that governs the growth rate of $c_n$, and if we happen to know a particular $c_n$ that gives a rigourous upper bound on $\mu$, namely $\mu \leq c_n^{1/n}$.

On page 10 of Madras and Slade's 1993 book "The self-avoiding walk", a better bound for $\mu$ is given: $$ \mu \leq \left(\frac{c_n}{c_1}\right)^\frac{1}{n-1} ~~~~~(n \geq 2). $$
This bound is attributed to Alm, but the only reference is to an unpublished manuscript of Ahlberg and Janson from 1980.

Does anyone know a good proof/reference for this bound? It would be implied by submultiplicativity of $a_n := c_{n+1}/c_1$, which in turn would be implied by the inequality $c_{n+m-1}c_1 \leq c_nc_m$ for all $n, m \geq 1$.


Maybe it's in Sven Erick Alm, Upper bounds for the connective constant of self-avoiding walks, Combin. Probab. Comput. 2 (1993), no. 2, 115–136, MR1249125 (94g:60126). The summary is,

We present a method for obtaining upper bounds for the connective constant of self-avoiding walks. The method works for a large class of lattices, including all that have been studied in connection with self-avoiding walks. The bound is obtained as the largest eigenvalue of a certain matrix. Numerical application of the method has given improved bounds for all lattices studied, e.g., $\mu\lt2.696$ for the square lattice, $\mu\lt4.278$ for the triangular lattice and $\mu\lt4.756$ for the simple cubic lattice.


The number $a_n=c_{n+1}/c_1$ represents the number of SA walks of length $n+1$ which make the first step to the right. Thus, $a_n$ counts obstructed SA walks of length $n$ with an obstacle placed to the left of their starting point.

This explains why $a_n$ is submultiplicative - every obstructed walk of length $m+n$ is the concatenation of an obstructed walk of length $m$ with a (rotated) obstructed walk of length $n$, where the obstacle for the second part of the walk is the penultimate vertex of the first part.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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