 Solution

A self-avoiding walk of length $n$ is a sequence of $n+1$ distinct graph vertices joined consecutively by edges. Split a rooted self-avoiding walk of length $m+n$ after $m$ steps. There are ${\kappa }_m$ possible prefixes; each remaining segment is a self-avoiding $n$-step walk from its current graph vertex, and forbidding intersections with the prefix can only reduce its count below ${\kappa }_n$. Translation invariance therefore givesApply the Fekete lemma, proved in Question 4(a), to $\log {\kappa }_n$. It gives $\log \mu ={\inf }_n{n}^{-1}\log {\kappa }_n$ and hence existence of the connective constant. Walks using only the $d$ positive coordinate directions never revisit a graph vertex, so there are at least $d^n$. A walk has $2d$ choices for its first step and at most $2d-1$ subsequently because immediate reversal is forbidden. Thus

For independent bond percolation, let $C(0)$ be the percolation cluster of the origin, $\theta (p)=P_p(|C(0)|=\infty )$, and $p_c=\inf \{p:\theta (p)>0\}$. An infinite percolation cluster in a locally finite graph contains an open self-avoiding path of every length. The union bound givesWhen $p\mu <1$, the right-hand side tends to zero, since its $n$th root tends to $p\mu$. Hence the connective-constant lower bound for percolation is

For the upper bound in two dimensions, use the square planar dual graph. Call a dual edge available when its crossing primal edge is closed. Each dual edge is available with probability $q=1-p$, independently. The planar graph boundary lemma says that a finite primal percolation cluster is enclosed by a graph cycle consisting of such edges: its external edge boundary gives this graph cycle. We show that $q\mu <1$ guarantees positive percolation probability.

Let $N_n$ count enclosing graph cycles of length $n$. Because the origin lies inside their coordinate bounding box and their diameter is at most $n$, every such graph cycle has a graph vertex within a box of side $2n+3$. From each possible root, the first $n-1$ edges give a self-avoiding walk; the final closing edge is then determined. Dropping the closure restriction gives the convenient boundChoose $\rho$ with $q\mu <\rho <1$. The connective-constant limit of a sequence implies ${\kappa }_{n-1}{q}^n\le C{\rho }^n$. Consequently the large-circuit tailis summable.

Condition all primal edges inside a large square $[-L,L{]}^2$ to be open; this event has positive probability. The origin percolation cluster then contains that square. If it is finite, its enclosing graph cycle has length at least $L$. A proposed graph cycle using a pinned-open edge now has conditional probability zero; every other proposed graph cycle still has probability $q^n$ by independence of random variables. For $L$ large enough the union bound for the remaining graph cycles is less than one. There is therefore positive conditional probability that the origin percolation cluster is infinite. This proves the connective-constant Peierls bound without needing the exact value of $p_c$: