Connective constants of Grigorchuk graphs

Abstract

The connective constant $\mu (G)$ of a graph $G$ is the exponential growth rate of the number of self-avoiding walks starting at a given vertex. We prove upper and lower bounds for the connective constants of Cayley graphs $G_{\omega }$ of a general Grigorchuk group encoded by a sequence $\omega \in \{0,1,2{\}}^{\mathbb{N}}$. In particular, $\mu (G_{\omega })>\varphi$ for any such Cayley graph (subject to a simple condition on $\omega$), where $\varphi :=\frac{1}{2}(1+\sqrt{5})$ is the golden mean. This extends earlier work of the author and Zhongyang Li in "Cubic graphs and the golden mean'', Discrete Math. 343 (2020), article 111638, where it was conjectured that $\mu (G)\ge \varphi$ for all infinite, vertex-transitive, cubic graphs. The current work includes an analysis of the proportions of appearances of given label-sequences in the orbital Schreier graphs of general Grigorchuk groups.