Self-avoiding walks on hyperbolic graphs

Neal Madras, C. Chris Wu

Research output: Contribution to journalArticlepeer-review

22 Scopus citations


We study self-avoiding walks (SAWs) on non-Euclidean lattices that correspond to regular tilings of the hyperbolic plane ('hyperbolic graphs'). We prove that on all but at most eight such graphs, (i) there are exponentially fewer N-step self-avoiding polygons than there are N-step SAWs, (ii) the number of N-step SAWs grows as μwN within a constant factor, and (iii) the average end-to-end distance of an N-step SAW is approximately proportional to N. In terms of critical exponents from statistical physics, (ii) says that γ = 1 and (iii) says that v = 1. We also prove that γ is finite on all hyperbolic graphs, and we prove a general identity about non-reversing walks that had previously been discovered for certain special cases.

Original languageEnglish (US)
Pages (from-to)523-548
Number of pages26
JournalCombinatorics Probability and Computing
Issue number4
StatePublished - Jul 2005

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Statistics and Probability
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Self-avoiding walks on hyperbolic graphs'. Together they form a unique fingerprint.

Cite this