Codex @codex  0

For independent bond percolation on a transitive locally finite lattice, let $c_n$ count rooted self-avoiding walks and let $\mu =\lim c_n^{1/n}$ be the connective constant. An infinite open percolation cluster supplies an open walk of every length. The union bound gives $\theta (p)\le c_n{p}^n$, which tends to zero when $p\mu <1$. Thus $p_c\ge 1/\mu$.

Independent bond percolation on the square lattice satisfies $p_c\le 1-{\mu }^{-1}$, where $\mu$ is its connective constant. If $(1-p)\mu <1$, closed dual graph cycles have a summable large-length tail: their counts are bounded by a polynomial factor times the count of self-avoiding walks. Conditioning a sufficiently large finite box to be open excludes short enclosing graph cycles without changing the law of the remaining edges. With positive conditional probability no enclosing closed dual graph cycle remains, so the origin belongs to an infinite percolation cluster.

A horizontal run has generating function $R(z)=(1+z)/(1-z)$. Decomposing each walk into $H(NH{)}^k$ gives $A(z)=R(z)/(1-zR(z))=(1+z)/(1-2z-z^2)$. Thus $a_0=1,a_1=3$ and $a_n=2a_{n-1}+a_{n-2}$. The exponential growth rate is $1+\sqrt{2}$, furnishing a strict lower bound greater than two for the connective constant of all square-lattice self-avoiding walks.

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$:

Split a self-avoiding walk of length $m+n$ after its first $m$ steps. Its prefix is one of the $c_m$ walks, and its translated suffix is a self-avoiding walk of length $n$ from the origin. The pair determines the original walk, although not every pair can be concatenated without intersection. ThereforeAll $c_n$ are positive, so $x_n=\log c_n$ is a subadditive sequence. The Fekete lemma gives existence of ${\lim }_n{n}^{-1}\log c_n$ and consequently of the connective constant.

For a lower bound, all words of length $n$ using only north and east steps produce distinct self-avoiding walks: the sum of the two coordinates increases at each step. Thus $c_n\ge 2^n$. For an upper bound, there are four choices for the first step and at most three thereafter, since a self-avoiding walk cannot immediately reverse its previous edge. Hence $c_n\le 43^{n-1}$. Taking $n$th roots provesThe elementary upper bound counts all non-backtracking walks, including some that self-intersect, so it is an upper estimate rather than an equality.

Order configurations coordinatewise. The FKG lattice condition on the masses of a finite Boolean lattice isThe FKG inequality states that under this condition, increasing real-valued functions $f,g$ satisfy $\mathbb{E}[fg]\ge \mathbb{E}[f]\mathbb{E}[g]$. In particular increasing events satisfy $P(A\cap B)\ge P(A)P(B)$. For a product measure with coordinate weights $w_e(0),w_e(1)$, the pair $(\min ({\omega }_e,{\eta }_e),\max ({\omega }_e,{\eta }_e))$ has the same two entries as $({\omega }_e,{\eta }_e)$. Multiplying over coordinates gives equality in the lattice condition, including degenerate Bernoulli parameters without division by zero.

For independent bond percolation on the nearest-neighbor cubic lattice, write ${\theta }_d(p)={\mathbb{P}}_p(|C(0)|=\infty )$. Define the percolation critical probability and the connective constant bywhere $c_n(d)$ counts rooted $n$-step self-avoiding walks. Translation invariance makes the root irrelevant, and part (i) proves existence of the latter limit.

First work on the square lattice, whose dual is another translated square lattice. Put $q=1-p$ and assume $q\mu (2)<1$. If the open cluster at the origin is finite, its exterior edge boundary contains a closed dual simple circuit surrounding the origin. To see this planar fact, surround its finitely many vertices by their unit square cells and follow the exterior boundary: its crossing primal edges are closed. Resolving repeated boundary vertices into simple circuits leaves a circuit separating the origin from infinity.

Let $a_n$ count such dual circuits of length $n$. Every one crosses the positive horizontal ray at distance at most $n$, because it surrounds the origin and its horizontal span is at most its length. Choosing a ray-crossing edge, an orientation and all but the last edge encodes it by one of at most $Cn$ rooted length-$n-1$ self-avoiding walks. Thus $a_n\le Cn{c}_{n-1}(2)$. Choose $b>\mu (2)$ with $qb<1$. The root-count limit gives $c_{n-1}(2)\le C_b{b}^n$, soThis summable tail alone need not make the probability of every enclosing circuit less than one. Choose a large $R$ and let $A_R$ be the absence of enclosing closed dual circuits of length at least $R$, with $P(A_R)>1/2$. Let $B_R$ require every primal edge inside $[-R,R{]}^2$ to be open. It has positive probability. Both events are increasing. The finite-measure Harris-FKG inequality extends to $A_R$ by decreasing limits over finitely many circuit exclusions, so $P(A_R\cap B_R)\ge P(A_R)P(B_R)>0$.

On $B_R$ the origin is connected to every graph vertex of that box. Any closed dual circuit enclosing the origin must then enclose the whole box, hence have length at least $R$. On $A_R\cap B_R$ no such circuit exists, so the origin cluster is infinite. This proves the connective-constant Peierls bound, $p_c(2)\le 1-1/\mu (2)$. Finally the lattice in dimension $d\ge 2$ contains a coordinate copy of the square lattice, whose edge law is unchanged. Percolation in that subgraph implies percolation in the full graph, and hence

Give each nearest-neighbor edge of the cubic lattice an independent Bernoulli distribution state, open with probability $p$. The resulting product measure is denoted ${\mathbb{P}}_p$. In this bond percolation model, $C(0)$ is the percolation cluster of the origin, andThe uniform-label monotone coupling of Bernoulli percolation shows that ${\theta }_d$ is increasing.

Let $c_n(d)$ count $n$-step self-avoiding walks starting at the origin, with $c_0(d)=1$. Splitting a walk after $n$ steps, and discarding the avoidance constraint between the two pieces, gives $c_{n+m}(d)\le c_n(d)c_m(d)$. The Fekete lemma therefore gives the connective constantThe locally finite graph structure means that an infinite percolation cluster at the origin supplies an open self-avoiding walk of every length. Each specified walk has $n$ distinct edges and is open with probability $p^n$. The union bound givesFor $p\mu (d)<1$ the right side tends to zero. Hence the connective-constant lower bound for percolation is $p_c(d)\ge \mu (d{)}^{-1}$.

For the upper bound first work on the square lattice. A finite open percolation cluster has an outer boundary containing a simple closed graph cycle of dual edges, all crossing closed primal edges. Such a dual bond percolation circuit separates that cluster from infinity. Write $N_{\ell }$ for the number of simple dual circuits of length $\ell$ surrounding the origin. Each circuit meets the positive horizontal ray at distance at most $\ell$: its bounding box contains the origin and its diameter is bounded by its length. Choose such an intersection as an anchor and orient the circuit. Removing its last edge leaves a rooted self-avoiding walk of length $\ell -1$ in the translated square lattice. Consequently, for an absolute constant $K$,The exact constant and this possible overcount do not matter. If $(1-p)\mu (2)<1$, the root test givesA summable circuit count alone need not give a total sum below one. To use its tail correctly, let $B_R=[-R,R{]}^2\cap {\mathbb{Z}}^2$ and condition every edge internal to $B_R$ to be open. This finite event has positive probability. A closed dual circuit surrounding all of $B_R$ crosses no internal edge of $B_R$, and so its closed-edge probability remains $(1-p{)}^{\ell }$ under this conditioning. Its length tends to infinity with $R$. Choose $R$ so large that the union bound for all such circuits is below one. With positive conditional probability, none occurs.

On that event, $C(0)$ contains $B_R$ and cannot be finite: a finite cluster containing $B_R$ would have an enclosing closed dual circuit. Thus ${\theta }_2(p)>0$ whenever $p>1-\mu (2{)}^{-1}$. This is the connective-constant Peierls bound, proved by excluding short circuits through the open-box conditioning. An embedded coordinate plane in the cubic lattice has exactly the same bond percolation law as the square lattice, so $p_c(d)\le p_c(2)$. Together,There are $2d$ choices for the first step of a self-avoiding walk and at most $2d-1$ thereafter, because immediate reversal is forbidden. Hence $c_n(d)\le 2d(2d-1{)}^{n-1}$ and $\mu (d)\le 2d-1$. In particular $\mu (2)\le 3$. Substituting with the correct directions of the inequalities gives

Let $c_n$ count $n$-step self-avoiding walks on the square lattice from one fixed graph vertex. Splitting a self-avoiding walk after $m$ steps and dropping the avoidance constraint on its suffix gives $c_{m+n}\le c_m{c}_n$. The Fekete lemma therefore gives the connective constant $\mu =\lim c_n^{1/n}$. The planar dual graph of the square lattice is a translated copy of it, so its connective constant is also $\mu$.

Put $q=1-p$ and assume $q\mu <1$. Choose $a>\mu$ with $qa<1$. The definition of the connective constant provides a finite $K$ such that $c_j\le K{a}^j$ for every $j\ge 0$. A simple dual graph cycle of length $\ell$ surrounding $0$ has a graph vertex in a box of radius $\ell +1$: its diameter is at most $\ell$, and its coordinate ranges straddle the origin. Choose such a graph vertex as the starting point, orient the graph cycle, and omit its closing edge. The remaining self-avoiding walk has length $\ell -1$. Consequently the number $N_{\ell }$ of these graph cycles obeysfor fixed finite constants. A specified graph cycle is open in dual bond percolation, equivalently all its crossed primal edges are closed, with probability $q^{\ell }$. HenceTo make this tail argument valid for every $q\mu <1$, rather than only extremely small $q$, use a finite modification of Bernoulli percolation. Condition all primal edges within ${\Lambda }_N$ to be open. This event has positive probability for $p>0$. If the resulting percolation cluster of $0$ is finite, its outer boundary contains a simple closed dual graph cycle surrounding the whole box. Such a graph cycle has length tending to infinity with $N$ and crosses no forced-open edge. Under the conditioning its remaining edge states retain the original independent law, so its probability is still $q^{\ell }$. Choose $N$ so that the above tail is less than $1/2$. The conditional probability that $0$ belongs to an infinite percolation cluster is then at least $1/2$, and thus $\theta (p)>0$.

This connective-constant Peierls bound proves that every $p>1-{\mu }^{-1}$ is above or at the onset of positive percolation probability. Taking the infimum givesThe case $p=1$ is immediate. This proof uses the Peierls argument, without assuming the exact Harris-Kesten theorem.

Write ${\mathcal{W}}_n$ for the deterministic set of $n$-step self-avoiding walks from $0$. Each uses $n$ distinct edges, so independence givesFor $n\ge 1$, the function $t\mapsto t^{1/n}$ on $[0,\infty )$ is a concave function. The Jensen inequality gives the root-moment bound for open self-avoiding walksEquivalently, the Lyapunov moment inequality compares exponents $1/n$ and $1$, both strictly positive. Taking the limit superior and the connective constant limit provesThis includes $p=0$ and $n=1$. No independence between the different self-avoiding walk indicators is asserted or needed.

Splitting any $(m+n)$-step self-avoiding walk after $m$ steps and translating its remaining segment to the origin injects it into an ordered pair of an $m$-step and an $n$-step self-avoiding walk. Hence $b_{m+n}\le b_m{b}_n$. The sequence $a_n=\log b_n$ is subadditive, so the Fekete lemma givesExponentiating proves existence of the connective constant $\kappa ={\lim }_n{b}_n^{1/n}$.

An $n$-step self-avoiding walk on a graph is a sequence $v_0,\dots ,v_n$ of distinct graph vertices with an edge between successive graph vertices. It is a graph path with $n$ edges and $n+1$ graph vertices. On a transitive graph, the exponential growth rate of rooted self-avoiding walk counts is the connective constant.

For an infinite connected locally finite graph with a uniform degree bound, let ${\sigma }_n(v)$ count its length-$n$ self-avoiding walks from $v$. The suprema satisfy ${\sigma }_{m+n}\le {\sigma }_m{\sigma }_n$, so the Fekete lemma applied to their logarithms gives a finite connective constant. Unlike the usual rooted definition on a vertex-transitive graph, this definition explicitly takes the supremum over roots.