Counting self-avoiding walks

Geoffrey R. Grimmett, Zhongyang Li

Published 2013-04-26, updated 2015-03-22Version 2

The connective constant $\mu(G)$ of a graph $G$ is the asymptotic growth rate of the number of self-avoiding walks on $G$ from a given starting vertex. We survey three aspects of the dependence of the connective constant on the underlying graph $G$. Firstly, when $G$ is cubic, we study the effect on $\mu(G)$ of the Fisher transformation (that is, the replacement of vertices by triangles). Secondly, we discuss upper and lower bounds for $\mu(G)$ when $G$ is regular. Thirdly, we present strict inequalities for the connective constants $\mu(G)$ of vertex-transitive graphs $G$, as $G$ varies. As a consequence of the last, the connective constant of a Cayley graph of a finitely generated group decreases strictly when a new relator is added, and increases strictly when a non-trivial group element is declared to be a generator. Special prominence is given to open problems.