connective constant

A property of a lattice. Related to the rate at which the number of
self-avoiding walks on the lattice grows (c_n) with the
number of steps. Since it is known that the limit as n goes to
infinity of 1/n(log c_n) exists, it
is possible to define the value of the limit as being the growth
constant of the lattice, usually denoted by the Greek letter mu.
The connective constant is the logarithm of
this value, often denoted by the Greek letter kappa.

What is the connective constant of the two dimensional square lattice? (Other lattices can be treated similarly, but not much more is known -- let's keep it simple).

We'll show log 2 ≤ μ ≤ log 3.

To do this, we'll show:

1. At least 2^n-1 distinct self-avoiding walks of length n on the square grid;
2. No more than 4*3^n-2 distinct self-avoiding walks of length n exist on the square grid.

1. Consider the subset of ("monotone") paths starting from the origin which only step right or up. Clearly all these paths are self-avoiding, and equally clearly there are 2^n-1 of them.

   So there are at least 2^n-1 self-avoiding walks.

2. Now note that any self-avoiding walk never revisits any square, so in particular it never steps back. Thus, a self-avoiding walk has 4 choices for the first step, and at most 3 choices for every step after. (Of course, in practice there will often be fewer than 3 choices for the next step; we're just saying the walk cannot return to where it just came from!)

   So no more than 4*3^n-2 self-avoiding walks exist.

Using these techniques in d dimensions, we see that log d ≤ μ ≤ log (2d-1).