Self-avoiding walk

An $n$-step self-avoiding walk on a graph is a sequence $v_0,\dots ,v_n$ of distinct graph vertices with an edge between successive graph vertices. It is a graph path with $n$ edges and $n+1$ graph vertices. On a transitive graph, the exponential growth rate of rooted self-avoiding walk counts is the connective constant.

On the square lattice, a self-avoiding walk using north, east and west steps but no south steps. At each horizontal height, self-avoidance forces one monotone horizontal run. Conversely, such runs separated by north steps always give self-avoiding walks, because every new run is at a previously unvisited height.

A horizontal run has generating function $R(z)=(1+z)/(1-z)$. Decomposing each walk into $H(NH{)}^k$ gives $A(z)=R(z)/(1-zR(z))=(1+z)/(1-2z-z^2)$. Thus $a_0=1,a_1=3$ and $a_n=2a_{n-1}+a_{n-2}$. The exponential growth rate is $1+\sqrt{2}$, furnishing a strict lower bound greater than two for the connective constant of all square-lattice self-avoiding walks.

The generating function weights each self-avoiding walk by $x$ to the power of its length, including the zero-length walk. Its radius of convergence is the reciprocal of the upper exponential growth rate of the rooted counts, by the Cauchy-Hadamard theorem.

In a bipartite graph, a self-avoiding walk ends in its starting class exactly when it has even length. If degrees are bounded by $\Delta$, deleting the last edge gives ${\sigma }_{2k+1}\le \Delta {\sigma }_{2k}$ and hence $Z_G^0(x)\le Z_G(x)\le (1+\Delta x)Z_G^0(x)$ for $x\ge 0$. Thus these generating functions have the same radius of convergence.

Replace every degree-three vertex of a graph in one class of a bipartite graph by a triangle with one port for each incident edge. A self-avoiding walk whose endpoints remain in the other class cannot make two completed passages through the same triangle: each passage needs two unused ports and only three exist. Each old two-edge passage has exactly two replacements, of lengths three and four. Therefore the restricted generating functions satisfy $Z_H^0(x)=Z_G^0(\sqrt{x^3+x^4})$. If the old radius is $1/\mu$, the new radius obeys ${\rho }^3+{\rho }^4={\mu }^{-2}$.

In independent bond percolation on a graph, let $c_n$ be the number of $n$-step self-avoiding walks from a fixed graph vertex and ${\kappa }_n$ the number that are open. Then $\mathbb{E}{\kappa }_n=c_n{p}^n$. The Jensen inequality for the concave function $t^{1/n}$ gives $\mathbb{E}({\kappa }_n^{1/n})\le p{c}_n^{1/n}$. No independence between different self-avoiding walk indicators is needed. When $c_n^{1/n}\to \mu$, the limit superior is at most $p\mu$.

On the doubly infinite ladder graph, self-avoiding walks from a fixed graph vertex using only rightward or vertical steps are in bijection with words in $R,V$ containing no consecutive $V$ symbols. Their count is ${\sigma }_n=F_{n+2}$, since ${\sigma }_0=1$, ${\sigma }_1=2$, and ${\sigma }_n={\sigma }_{n-1}+{\sigma }_{n-2}$. Its exponential growth rate is the golden ratio.

If $b_n$ counts the $n$-step self-avoiding walks from a fixed vertex of a transitive lattice, the connective constant is the exponential growth rateSubmultiplicativity of $b_n$ and the Fekete lemma applied to $\log b_n$ prove existence of this limit.

For an infinite connected locally finite graph with a uniform degree bound, let ${\sigma }_n(v)$ count its length-$n$ self-avoiding walks from $v$. The suprema satisfy ${\sigma }_{m+n}\le {\sigma }_m{\sigma }_n$, so the Fekete lemma applied to their logarithms gives a finite connective constant. Unlike the usual rooted definition on a vertex-transitive graph, this definition explicitly takes the supremum over roots.