# Annales de l’Institut Henri Poincaré D

Full-Text PDF (311 KB) | Metadata | Table of Contents | AIHPD summary

**Volume 1, Issue 1, 2014, pp. 61–75**

**DOI: 10.4171/AIHPD/3**

Published online: 2014-02-04

Extendable self-avoiding walks

Geoffrey R. Grimmett^{[1]}, Alexander E. Holroyd

^{[2]}and Yuval Peres

^{[3]}(1) University of Cambridge, UK

(2) Microsoft Research, Redmond, USA

(3) Microsoft Research, Redmond, USA

The connective constant $\mu$ of a graph is the exponential growth rate of the number of $n$-step self-avoiding walks starting at a given vertex. A self-avoiding walk is said to be *forward* (respectively, *backward*) *extendable* if it may be extended forwards (respectively, backwards) to a singly infinite self-avoiding walk. It is called *doubly extendable* if it may be extended in both directions simultaneously to a doubly infinite self-avoiding walk. We prove that the connective constants for forward, backward, and doubly extendable self-avoiding walks, denoted respectively by
$\mu^F$, $\mu^B$, $\mu^{FB}$, exist and satisfy $\mu=\mu^F=\mu^B=\mu^{FB}$ for every infinite, locally finite, strongly connected, quasi-transitive directed graph. The proofs rely on a 1967 result of Furstenberg on dimension, and involve two different arguments depending on whether or not the graph is unimodular.

*Keywords: *Self-avoiding walk, connective constant, transitive graph, quasi-transitive graph, unimodular graph, growth, branching number

Grimmett Geoffrey, Holroyd Alexander, Peres Yuval: Extendable self-avoiding walks. *Ann. Inst. Henri Poincaré Comb. Phys. Interact.* 1 (2014), 61-75. doi: 10.4171/AIHPD/3