The EMS Publishing House is now EMS Press and has its new home at

Please find all EMS Press journals and articles on the new platform.

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 E., Peres Yuval: Extendable self-avoiding walks. Ann. Inst. Henri Poincaré Comb. Phys. Interact. 1 (2014), 61-75. doi: 10.4171/AIHPD/3