= 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 gives
$$
\kappa_{m+n}\le\kappa_m\kappa_n.
$$
Apply 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
$$
d^n\le\kappa_n\le2d(2d-1)^{n-1},\qquad\boxed{d\le\mu\le2d-1.}
$$
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> gives
$$
\theta(p)\le\kappa_np^n.
$$
When $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
$$
\boxed{p_c\ge\mu^{-1}.}
$$
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 bound
$$
N_n\le(2n+3)^2\kappa_{n-1}.
$$
Choose $\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 tail
$$
\sum_{n\ge L}N_nq^n\longrightarrow0\qquad(L\to\infty)
$$
is 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$:
$$
\boxed{p_c\le1-\mu^{-1}\quad(d=2).}
$$
Back to article page
