A language theoretic approach to self-avoiding walks

This thesis provides a study of self-avoiding walks on quasi-transitive graphs. The connective constant µ(G) of a graph G is the asymptotic growth rate of the number of self-avoiding walks on G starting at a given vertex. For a given graph height function mapping vertices of G to integers in a way adapted to the graph structure, a bridge is a self-avoiding walk such that the height of its vertices is bounded below by the height of the initial vertex and above by the height of the terminal vertex. If the roles of the initial and terminal vertices are reversed, we talk about reversed bridges. We show that for any graph height function, the maximum of the asymptotic growth rates of the number of bridges and the number of reversed bridges must be equal to the connective constant µ(G).

The main focus of this thesis is to apply the theory of formal languages to the study of self-avoiding walks. To this end, let G be a deterministically edge-labelled graph, that is, every (directed) edge carries a label such that any two edges starting at the same vertex have different labels. Then the set of all words which can be read along the edges of self-avoiding walks starting at o forms a language denoted by LSAW,o(G). We show that the properties of this language strongly depend on the end-structure of the graph G. It is regular if and only if all ends have size 1 and it is context-free if and only if all ends have size at most 2.

Making use of the class of multiple context-free languages, this characterisation can be extended even further. We show that LSAW,o(G) is a k-multiple context-free language if and only if the size of all ends of G is at most 2k. Applied to Cayley graphs of finitely generated groups this says that LSAW,o(G) is multiple context-free if and only if the group is virtually free. In this setting, using our method we also show that the ordinary generating function of self-avoiding walks is algebraic and in particular, the connective constant is an algebraic number.