Enumerating Self-Avoiding Walks on Grids

Dr. Naill Graham

Department of Computer Science
University of Alabama in Huntsville

May 15, 2002

Abstract

Since a path in a graph is "self-avoiding" by definition, we define a self-avoiding walk (SAW) on an infinite grid as simply a path from the origin. The determination of a precise asymptotic estimate for the number of self-avoiding walks of length n in a d-dimensional grid remains an unsolved problem. Some standard techniques from combinatorics, automata theory and linear algebra are applied to determine upper and lower bounds for the number of SAWs of length n. In the process the concept of state minimization is applied to non-negative matrices to produce a condition under which we may reduce a non-negative matrix to a smaller one without altering the number of walks it contains.