How to Avoid Yourself
Every Sunday morning you go for a walk in the city, heading nowhere in particular, with just one rule to your rambling: You never retrace your steps or cross your own path. If you have already walked along a certain block or passed through an intersection, you refuse to set foot there again.
This recipe for tracing a loopless path through a grid of city streets leads into some surprisingly dark back alleys of mathematics—not to mention byways of physics, chemistry, computer science and biology. Avoiding yourself, it turns out, is a hard problem. The exact analysis of self-avoiding walks has stumped mathematicians for half a century; even counting the walks is a challenge.
My own initiation into the trials of self-avoidance came when I began experimenting with a simple model of the folding of protein molecules, a story I told in an earlier "Computing Science" column (see Hayes 1998). Protein folding is close to the historical roots of the self-avoiding walk, which was first conceived as a tool for understanding the geometry of long-chain polymer molecules. A polymer writhing and wriggling in solution forms a random tangle—random, that is, except that no two atoms can occupy the same position at the same time. This "excluded volume effect" in the polymer is modeled by the walk's insistence on avoiding itself.
Self-avoiding walks have also found applications elsewhere in the sciences, such as the physics of magnetic materials and the study of phase transitions. And they are of interest as purely mathematical objects. Many of the obvious questions about them have resisted rigorous analysis, and so the best answers known so far come from computer-intensive methods.
All of the walks I shall describe here take place on a two-dimensional square lattice, which is a grid of city streets reduced to its mathematical essence. The lattice consists of all points on the plane that have integer x and y coordinates. Walks begin at the origin, the point with coordinates x=0 and y=0. A single step always moves from the current lattice site to one of the four nearest-neighbor sites. By convention the length of a walk, n, is defined as the number of steps, and so the number of lattice sites visited is n + 1.