Consider a regular lattice, such as the hypercubic lattice in d-dimensional Euclidean space. For simplicity, consider the two dimensional case, which is the square lattice. A self-avoiding walk is an alternating sequence of vertices and edges, in which successive pairs of vertices are unit distance apart, and are joined by an edge. All vertices of the walk are distinct. That is, no two vertices can occupy the same point in the lattice. We can ask for the number of self-avoiding walks with n edges, c(n), where two walks are considered to be distinct if they cannot be superimposed by translation. For instance, for the square lattice c(1)=4, c(2)=12, c(3)=36 and c(4)=100. A long-standing open question is to find a closed form expression for c(n). There is a proof (by John Hammersley, Proc. Camb. Phil. Soc. in 1957) that c(n) increases exponentially rapidly, and upper and lower bounds are known.

Other interesting questions concern the typical spatial dimensions of a self-avoiding walk. For instance, how does the mean square radius of gyration of an n-step self-avoiding walk depend on n? Practically nothing is known rigorously about these questions.

One can generalise the self-avoiding walk problem in various ways. One is to consider the number of embeddings (in a specified lattice) of graphs with a fixed homeomorphism type. Christine Soteros has some very interesting results about this problem. Another is to consider walks in a lattice subset, which amounts to asking how the number of walks is affected by imposing a geometrical constraint. One can also add a short-range attractive potential between pairs of vertices of the walk, and this gives a useful model of the collapse transition in linear polymers.

The standard reference on self-avoiding walks is ``The Self-Avoiding Walk'' by Neal Madras and Gordon Slade.