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.