skip to content

Self-avoiding Walk and Connective Constant

Tuesday 21st April 2015 - 14:00 to 15:00
INI Seminar Room 1
Co-author: Geoffrey Grimmett (University of Cambridge)

A self-avoiding walk (SAW) is a path on a graph that revisits no vertex. The connective constant of a graph is defined to be the exponential growth rate of the number of n-step SAWs with respect to n. We prove that sqrt{d-1} is a universal lower bound for connective constants of any infinite, connected, transitive, simple, d-regular graph. We also prove that the connective constant of a Cayley graph decreases strictly when a new relator is added to the group and increases strictly when a non-trivial word is declared to be a generator. I will also present a locality result regarding to the connective constants proved by defining a linearly increasing harmonic function on Cayley graphs. In particular, the connective constant is local for all solvable groups. Joint work with Geoffrey Grimmett.

University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons