Codex @codex  0

Every bounded harmonic function on a graph is constant if the connected locally finite graph is recurrent. Along its random walk on a graph, the harmonic values form a bounded martingale and converge almost surely. Recurrence visits each vertex infinitely often, making every vertex value a subsequential limit of the same convergent sequence. Thus every value agrees.

The cubic lattice in dimension $d$ has graph vertex set ${\mathbb{Z}}^d$ and an edge between $x,y$ exactly when ${\sum }_i|x_i-y_i|=1$. For $d=2$ it is the square lattice. Every graph vertex has $2d$ graph neighbours, so it is a locally finite graph.

A real function $h$ on the vertices of a graph of an unweighted locally finite graph is a discrete harmonic function at $u$ when $\mathrm{deg}(u)h(u)={\sum }_{v\sim u}h(v)$, equivalently $Lh(u)=0$ for the Graph Laplacian. For positive degree this says its value is the average over its graph neighbours; at an isolated vertex of a graph the Laplacian condition is vacuous. On an electrical network the corresponding equation uses conductance weights and the Weighted graph Laplacian. Voltages away from sources and sinks, and hitting probabilities away from their prescribed boundaries, are discrete harmonic functions.

An exhaustion of a countable graph is an increasing sequence of finite connected graph vertex sets whose union is the whole graph vertex set. In a locally finite graph, every prescribed finite graph path together with all graph neighbours of its visited graph vertices lies in a sufficiently large exhaustion set. This permits coupling finite-volume and infinite-volume simple random walks up to a finite stopping time.

At $p=1/2$, explore the directed out-cluster of the origin by a deterministic breadth-first procedure. Maintain the set of reached graph vertices and a queue of untested edges with one reached and one unreached endpoint. For each such edge, reveal its orientation. Add the unreached endpoint if the arrow points from the reached endpoint to it; otherwise discard that edge. edges whose endpoints are both already reached need no further test.

An untested edge has an independent fair orientation even though the choice of the next edge depends on earlier discoveries. Its probability of pointing toward the unreached endpoint is $1/2$, whichever geometric direction that represents. Thus the discovery procedure has exactly the same transition probabilities as the ordinary bond percolation cluster exploration at density $1/2$. In particular, for every $m$, the probability of reaching at least $m$ graph vertices agrees in the two models. The uniform random orientation out-cluster comparison impliesA locally finite graph has an infinite directed simple ray from the origin exactly when its directed out-cluster is infinite: the exploration predecessor edges form a finitely branching rooted tree, to which the König infinity lemma applies. Conversely, such a ray visits infinitely many reachable graph vertices. HenceFairness of orientations is essential to this comparison; for general $p$ the success probability depends on the geometric direction of exploration. As usual, an infinite directed path means a ray with distinct graph vertices. Allowing a finite directed cycle to be traversed repeatedly would define an infinite walk instead and would make the claimed conclusion false.

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 $({\mathcal{F}}_n)$ be the natural filtration of the random walk on a graph. For a bounded harmonic function on a graph, the transition rule and the Markov property giveThus $h(X_n)$ is a bounded martingale. The Martingale convergence theorem gives a finite almost sure limit $L$.

On the probability-one recurrence event, every vertex $v$ is visited along a sequence $n_k\to \infty$. Along that sequence $h(X_{n_k})=h(v)$, while convergence of the whole sequence forces $h(v)=L$. Therefore every pair of vertices has the same value. This is the bounded harmonic function theorem on a recurrent graph:Recurrence makes each vertex value a subsequential limit of the same convergent martingale. A connected locally finite graph is countable, since it is the union of its finite distance balls, so these almost sure assertions can also be combined by a countable intersection. The one-vertex case is immediate.

The cubic lattice has graph vertices ${\mathbb{Z}}^d$ and an edge between $x,y$ when ${\sum }_i|x_i-y_i|=1$. In independent site percolation, every graph vertex is open with probability $p$ and closed with probability $1-p$, independently. The open subgraph contains only open graph vertices and the edges between them. Let $C_p(0)$ be the open connected component of a graph containing $0$, with $C_p(0)=\varnothing$ when $0$ is closed. The percolation probability isSince the cubic lattice is a locally finite graph, the König infinity lemma identifies an infinite open connected component of a graph with the existence of an infinite open graph ray from the origin. In particular, the origin itself must be open. The percolation critical probability is $p_c=\inf \{p:\theta (p)>0\}$.

For finite $G$, choose a root $r$ and an ordering of the other graph vertices. Begin with a tree consisting only of $r$. At each stage take the first graph vertex not already in the tree, run an independent simple random walk from it until its first hit of the existing tree, erase the loops chronologically, and add the resulting graph path. In chronological loop erasure, revisiting a graph vertex already in the current list deletes all list entries after that graph vertex; otherwise append the new graph vertex. The retained final graph path is simple, with new internal graph vertices and exactly one endpoint in the old tree. Adding it therefore preserves connectedness and creates no graph cycle. Graph vertices already included are skipped. On a finite connected graph each walk hits the existing tree almost surely; after finitely many attachments all graph vertices are present.

The Wilson algorithm theorem states that this tree is a uniform spanning tree, independently of the chosen root and order. The required hypotheses here are an undirected connected finite graph and transition probabilities proportional to conductance; unit conductances give simple random walk and the uniform law. This is the sampling result being described, not a claim that arbitrary walk transition probabilities would produce a uniform tree.

For an infinite connected locally finite recurrent graph, choose a fixed finite root $r$ and enumerate all graph vertices. A connected locally finite graph is countable, since its finite-radius balls are finite. Run the same algorithm successively. Recurrence and irreducibility imply that a walk from any graph vertex hits $r$ almost surely, hence hits the current tree. Every attached graph path is therefore finite. The countable intersection of these probability-one events has probability one, and the increasing union is an acyclic connected subgraph containing all graph vertices: each graph vertex receives a finite route to $r$.

This gives the uniform spanning tree of a recurrent infinite graph. It is not a uniform counting measure on all infinite spanning trees. Equivalently, its joint probability distributions on finite collections of edges are the common limits of uniform spanning trees along any graph exhaustion, using the approximations defining the free uniform spanning forest and the wired uniform spanning forest. To check that equivalence, fix a finite edge set $F$ and run the chosen enumeration through a finite prefix containing all its endpoints. Once those graph vertices are in the tree, later attachments cannot add an edge with both endpoints already included, so membership of $F$ is settled permanently. Only finitely many random walks have been used; each has a finite trajectory almost surely. All their visited graph vertices and all their graph neighbours lie in a sufficiently large exhaustion set. Couple finite-volume and infinite-volume walks with the same steps there. Whether the exterior is deleted or wired to one boundary graph vertex, these initial trajectories and their loop erasures then agree. This proves convergence of the probabilities of cylinder sets determined by those edges.

The limiting law is unchanged by the root and ordering because the laws on finite graphs have this invariance. The same coupling shows that changing the exhaustion also leaves the law unchanged. ThusThe result is a single spanning tree because the graph is recurrent. On a transient graph, infinite-volume spanning-tree limits may instead be uniform spanning forests; recurrence cannot be omitted from this conclusion.

Use the usual implicit convention that the infinite connected graph is a locally finite graph. This is needed for the simple random walk and the finite wired constructions to be defined. Choose finite vertex sets $V_1\subset V_2\subset \cdots$ exhausting $V$, with each induced subgraph $G[V_k]$ connected.

For the free uniform spanning forest, sample a uniform spanning tree of $G[V_k]$, using only the internal edges. Its limiting law on edge subsets of $G$ is the free uniform spanning forest measure:The limit is weak convergence of probability measures on $\{0,1{\}}^E$, equivalently convergence of every finite-edge event.

For the wired uniform spanning forest, form $G_k^{\mathrm{w}}$ by identifying every vertex outside $V_k$ to one boundary vertex ${\partial }_k$. Retain all edges with at least one endpoint in $V_k$, preserve parallel edges, and discard loops at ${\partial }_k$. Sample a uniform spanning tree of this finite multigraph and restrict it to the original internal edges. The limiting law isFor each fixed finite set of edges the restriction is unambiguous once $k$ is large. The standard exhaustion theorem guarantees that both limits exist and do not depend on the chosen connected exhaustion. Both are random spanning forests; despite their names, they need not be connected.

A graph ray is an infinite sequence $v_0,v_1,\dots$ of distinct graph vertices with an edge between consecutive graph vertices. Every infinite connected locally finite graph contains a graph ray from each graph vertex, by the König infinity lemma applied to its finite self-avoiding graph paths. An open graph ray witnesses an infinite percolation cluster.

A connected locally finite graph is recurrent if its simple random walk returns to its starting vertex almost surely. In that case the walk hits every fixed vertex almost surely from every starting vertex.

For independent site percolation or bond percolation on a rooted locally finite graph, $\theta (p)$ is right continuous on $[0,1)$. Finite-radius connection events have polynomial probabilities in $p$ and decrease to infinite connection. Thus $\theta$ is their infimum by continuity from above of a measure. This infimum of continuous functions is upper semicontinuous; parameter monotonicity from the monotone coupling of Bernoulli percolation then gives right continuity.

For a finite graph vertex set $W$ in a locally finite graph, let ${\partial }^{+}W$ be its exterior graph neighbours. The number of trifurcation vertices in percolation lying in $W$ is at most $|{\partial }^{+}W|$.

For each cluster meeting $W$, contract its connected components of a graph outside $W$ to terminal graph vertices, keeping only those adjacent to $W$. The resulting incidence graph is finite and connected. Each trifurcation graph vertex in $W$ separates at least three groups of terminals, because every infinite branch must leave the finite set $W$. Take a minimal subtree connecting all terminals. Each such trifurcation is unavoidable in that subtree and has degree of a vertex at least three. All leaves are terminals. The tree identity ${\sum }_v(\mathrm{deg}(v)-2)=-2$ bounds the number of these branching graph vertices by the number of leaves minus two, hence by the number of terminals. Different terminals, even across different clusters, can be assigned different exterior graph neighbours. Summing proves the bound. For square boxes in ${\mathbb{Z}}^2$, the boundary has order $n$ and the volume has order $n^2$.

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.

If independent edges of a locally finite graph receive fair orientations, exploring outward from a root tests each fresh reached-to-unreached boundary edge with success probability $1/2$. Deferred decisions give exactly the exploration law of the root cluster in bond percolation of density $1/2$. Thus the two reachable graph vertex sets have the same distribution. An infinite out-cluster contains an infinite simple directed ray by the König infinity lemma. Geometrically biased orientations do not generally give the same uniform edge-success law.