Extendable self-avoiding walks

  • Geoffrey R. Grimmett

    University of Cambridge, UK
  • Alexander E. Holroyd

    Microsoft Research, Redmond, USA
  • Yuval Peres

    Microsoft Research, Redmond, USA


The connective constant of a graph is the exponential growth rate of the number of -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 , , , exist and satisfy 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.

Cite this article

Geoffrey R. Grimmett, Alexander E. Holroyd, Yuval Peres, Extendable self-avoiding walks. Ann. Inst. Henri Poincaré Comb. Phys. Interact. 1 (2014), no. 1, pp. 61–75

DOI 10.4171/AIHPD/3