Self-avoiding walks and connective constants


Abstract in English

The connective constant $mu(G)$ of a quasi-transitive graph $G$ is the asymptotic growth rate of the number of self-avoiding walks (SAWs) on $G$ from a given starting vertex. We survey several aspects of the relationship between the connective constant and the underlying graph $G$. $bullet$ We present upper and lower bounds for $mu$ in terms of the vertex-degree and girth of a transitive graph. $bullet$ We discuss the question of whether $mugephi$ for transitive cubic graphs (where $phi$ denotes the golden mean), and we introduce the Fisher transformation for SAWs (that is, the replacement of vertices by triangles). $bullet$ We present strict inequalities for the connective constants $mu(G)$ of transitive graphs $G$, as $G$ varies. $bullet$ 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 further generator. $bullet$ We describe so-called graph height functions within an account of bridges for quasi-transitive graphs, and indicate that the bridge constant equals the connective constant when the graph has a unimodular graph height function. $bullet$ A partial answer is given to the question of the locality of connective constants, based around the existence of unimodular graph height functions. $bullet$ Examples are presented of Cayley graphs of finitely presented groups that possess graph height functions (that are, in addition, harmonic and unimodular), and that do not. $bullet$ The review closes with a brief account of the speed of SAW.

Download