Open Access Publications from the University of California

## Published Web Location

https://doi.org/10.5070/C63160431
Abstract

Let $$G$$ be a quasi-transitive, locally finite, connected graph rooted at a vertex $$o$$, and let $$c_n(o)$$ be the number of self-avoiding walks of length $$n$$ on $$G$$ starting at $$o$$. We show that if $$G$$ has only thin ends, then the generating function $$F_{\mathrm{SAW},o}(z)=\sum_{n \geq 1} c_n(o) z^n$$ is an algebraic function. In particular, the connective constant of such a graph is an algebraic number.

If $$G$$ is deterministically edge-labelled, that is, every (directed) edge carries a label such that no two edges starting at the same vertex have the same label, 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 $$L_{\mathrm{SAW},o}$$. Assume that the group of label-preserving graph automorphisms acts quasi-transitively. We show that $$L_{\mathrm{SAW},o}$$ 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 $$L_{\mathrm{SAW},o}$$ is multiple context-free if and only if the group is virtually free.

Mathematics Subject Classifications: 20F10, 68Q45, 05C25

Keywords: Self avoiding walk, formal language, multiple context free language, Cayley graph, virtually free group