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:
- At least 2n-1 distinct self-avoiding walks of length n on the square grid;
- No more than 4*3n-2 distinct self-avoiding walks of length n exist on the square grid.
s and limit
s (more properly, lim infs and lim sups)
, we shall see the desired bounds on μ.
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 2n-1 of them.
So there are at least 2n-1 self-avoiding walks.
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*3n-2 self-avoiding walks exist.
Using these techniques in d dimensions, we see that log d ≤ μ ≤ log (2d-1).