64c3814
==== TABLE OF CONTENTS ====
No-percolation-at-criticality-on-quasi-transitive-graphs//assembly.tex
No-percolation-at-criticality-on-quasi-transitive-graphs//corridor-exploration.tex
No-percolation-at-criticality-on-quasi-transitive-graphs//corridors.tex
No-percolation-at-criticality-on-quasi-transitive-graphs//gluing.tex
No-percolation-at-criticality-on-quasi-transitive-graphs//interpolation.tex
No-percolation-at-criticality-on-quasi-transitive-graphs//introduction.tex
No-percolation-at-criticality-on-quasi-transitive-graphs//main.tex
No-percolation-at-criticality-on-quasi-transitive-graphs//moves.tex
No-percolation-at-criticality-on-quasi-transitive-graphs//preliminaries.tex
No-percolation-at-criticality-on-quasi-transitive-graphs//sections/interpolation.tex
No-percolation-at-criticality-on-quasi-transitive-graphs//sections/moves.tex
No-percolation-at-criticality-on-quasi-transitive-graphs//structure.tex
No-percolation-at-criticality-on-quasi-transitive-graphs//superpolynomial.tex
No-percolation-at-criticality-on-quasi-transitive-graphs//two-cluster-dfs-entropy.tex
No-percolation-at-criticality-on-quasi-transitive-graphs//references.bib
===========================
==== BEGIN No-percolation-at-criticality-on-quasi-transitive-graphs//assembly.tex ====
\section{Completion and the lattice consequence}
\label{sec:completion}
\begin{proof}[Proof of Theorem~\ref{thm:main}]
The reduction in Section~\ref{sec:preliminaries} permits us to work
with a simple graph. By Lemma~\ref{lem:orbit-growth}, its uniform
exponential growth rate exists. If this rate is greater than one,
Theorem~\ref{thm:exponential} applies. Otherwise the graph has
subexponential growth.
In this remaining case, if \eqref{eq:superpoly-growth} holds,
Theorem~\ref{thm:superpoly} excludes critical percolation. If it does
not hold, \eqref{eq:polynomial-subsequence} holds along an unbounded
sequence. Proposition~\ref{prop:nilpotent-model} supplies the group
action required by Theorem~\ref{thm:structured}, which again excludes
critical percolation when $\pc<1$. Thus every fixed vertex has
probability zero of belonging to an infinite critical cluster.
The countable union over vertices proves the almost-sure assertion.
\end{proof}
\begin{corollary}
\label{cor:lattices}
For nearest-neighbor Bernoulli bond percolation on $\Z^d$, for every
$d\ge2$, there is almost surely no infinite cluster at the critical
probability. In particular this holds on $\Z^3$.
\end{corollary}
\begin{proof}
The graph is infinite, connected, locally finite, and transitive.
We verify $\pc<1$ by a planar boundary count on a coordinate copy
of $\Z^2$. If its origin cluster is finite, the dual edges crossing
its edge boundary contain a simple cycle surrounding the origin;
all crossed primal edges are closed. To see the existence of such
a cycle, the dual boundary has even degree at every vertex and
decomposes into simple cycles. The positive horizontal ray from
the origin crosses the whole boundary an odd number of times, so
one cycle crosses this ray oddly. A closed cycle crosses the whole
horizontal line evenly, and hence also crosses the negative ray.
A cycle of length $n$ therefore has a positive-ray crossing at
distance less than $n$ from the origin. Choosing that crossing,
an orientation, and a nonbacktracking continuation bounds the
number of candidates by $2n3^n$. Independence bounds the probability
that the origin cluster is finite by
\[
\sum_{n\ge1}2n3^n(1-p)^n.
\]
For $p<1$ sufficiently close to one this sum is less than one,
so planar percolation occurs with positive probability. The same
configuration is a subgraph of $\Z^d$, proving $\pc(\Z^d)<1$.
Theorem~\ref{thm:main} now applies.
\end{proof}
==== END No-percolation-at-criticality-on-quasi-transitive-graphs//assembly.tex ====
==== BEGIN No-percolation-at-criticality-on-quasi-transitive-graphs//corridor-exploration.tex ====
\section{Fresh corridors and a subcritical infinite cluster}
\label{sec:corridor-exploration}
Proposition~\ref{prop:moves} supplies paths with approximate coordinate
displacements $(1,1)$ and $(1,-1)$. We will use them to transfer a
connection through long corridors. The corridor axes have slopes $1/4$ and $-1/4$:
at each step, choosing the sign of the vertical move corrects the
path's displacement from its axis. The smaller slope leaves room for
this correction even when the entrance point is not prescribed.
The corridors form the bonds of an oriented square lattice, but their
vertex sets are coordinate preimages in $G$. All paths and revealed
edges remain in $G$. We will reveal an incoming corridor only after
estimating connections through the still fresh outgoing corridors.
This order will give a uniform conditional failure bound for each
tested lattice site.
\subsection{The deterministic layout}
The constant $C$ is the path-displacement bound from
Proposition~\ref{prop:moves}. Let $B$ be the initial vertical tolerance
for an entrance, and let $H$ be the tube half-width. Fix
\[
C=100,\qquad \mu=\tfrac14,\qquad B=2C+10,\qquad H=3B.
\]
An endpoint rectangle of time half-width $J$ will contain every overlap
of incident tubes. Choose that width first, and then the corridor
length, by taking integers $J,L$ with
\[
J>10(H/\mu+C),\qquad L>10(J+B),\qquad T=L+\tfrac12.
\]
For a site $v=(a,b)\in\mathbb N_0^2$, let
$c_v=((a+b)T,(a-b)\mu T)$. Its children are $(a+1,b)$ and
$(a,b+1)$; their displacement from $v$ is $(T,\sigma\mu T)$ with
$\sigma=1$ and $-1$, respectively. All regions below mean vertex
preimages under the coordinates $(t,z)$, with coordinates taken
relative to the indicated center. Define
\[
Q_v=\{|t-c_v^{(1)}|\le J,\
|z-c_v^{(2)}|\le\mu J+H\}.
\]
For a parent--child pair $v,x$ of sign $\sigma$, let $D_{vx}$ be the
induced subgraph on the union of $Q_v,Q_x$ and the tube
\[
0\le t-c_v^{(1)}\le T,\qquad
|z-c_v^{(2)}-\sigma\mu(t-c_v^{(1)})|\le H.
\]
Write $\mathcal E_{vx}$ for its edge set, and $\mathcal Q_v$ for
the edge set induced by $Q_v$.
\begin{lemma}[Corridor separation]\label{lem:corridors}
Distinct $Q_v$ are disjoint. Two distinct corridors with no common
endpoint have disjoint vertex sets; corridors sharing an endpoint $v$
intersect only in $Q_v$. A corridor misses every nonendpoint $Q_w$.
Consequently, common edges of incident corridors belong to
$\mathcal Q_v$ at their common endpoint.
\end{lemma}
\begin{proof}
Site layers are spaced by $T$ in the time coordinate; within a layer
their heights are spaced by $2\mu T$. The choices give
$T>2J$ and $\mu T>\mu J+H$, so the $Q$ regions are disjoint.
A tube near either endpoint layer has height differing from that
endpoint by at most $\mu J+H$ when its time differs by at most $J$.
It therefore misses every other $Q$ in that layer; other layers are
excluded by their time coordinates.
Tubes in nonadjacent layer intervals have disjoint time interiors.
At a common layer plane, distinct endpoint heights differ by
$2\mu T>2H$, so adjacent-layer tubes can meet only at a shared
endpoint, inside its $Q$. In the same layer interval, parallel tube
axes are separated by $2\mu T$. Oppositely sloped axes can approach
within $2H$ only when they share a start, within time $H/\mu$ of
that start, or share an end, within time $H/\mu$ of that end.
These intersections lie in the corresponding $Q$, since $J>H/\mu$.
Combining these tube facts with the $Q$ facts proves the vertex claims.
An edge in both induced subgraphs has both endpoints in their vertex
intersection, proving the last assertion. Edges joining different
corridors are never added merely because both their endpoints have
been revealed.
\end{proof}
\subsection{Relay regions and the order of scales}
\label{subsec:corridor-scales}
Inside a corridor we will place successive input regions near integer
times. Their vertical half-width decreases from $B$ by $1/2$ per step
until it reaches $2$. The local moves can make this correction because
their vertical displacement has magnitude one while the axis advances
only $\mu=1/4$. The final move will be stopped at the child mark,
halfway between the last two integer times.
For a vertex set $A$, its distance-$R$ collar is the ambient
neighborhood $\{x\in V(G):d_G(x,A)\le R\}$, where
$d_G(x,A)=\inf_{a\in A}d_G(x,a)$ and $\inf\varnothing=\infty$.
We need each input region's collar to contain many disjoint finite
seed trials. The collar may be wide in graph distance while narrow in
coordinates, because the edge-coordinate bound is chosen last.
Let $\varepsilon$ be the permitted conditional probability of a failed
lattice site. Choose it so small that
\begin{equation}\label{eq:directed-contour-series}
\sum_{l\ge1}4^l\varepsilon^{l/4}<1.
\end{equation}
The threshold $\delta$ will test stored connection probabilities;
$\kappa$ will bound the loss at a single relay. Set
\[
\delta=\varepsilon/4,\qquad
\kappa=\frac{\varepsilon\delta}{8(L+1)},\qquad
\lambda=\kappa/4,\qquad K=\log(4/\kappa).
\]
The transfer proof will use the auxiliary error $\lambda$ and trial
weight $K$. To keep accumulated endpoint errors below $1/100$, choose
$e>0$ with $(L+3)e<1/100$. Choose the failure probability of a seed
move to satisfy
\[
0<\eta_0\le\frac{\kappa\lambda}{4(K+1)}.
\]
Proposition~\ref{prop:moves}, with $e,\eta_0$, first gives a seed
radius $m$. We next choose the number $k$ of possible contacts needed
for disjoint seed trials and the graph-distance collar width $R$.
With $D$ the maximum degree, take integers
\begin{equation}\label{eq:corridor-trial-scales}
\begin{split}
k&>V_+(4m+2)
\left\lceil K/(\pc/2)^{m+1+V_+(m)}\right\rceil,\\
R&>m+4(1-\pc)^{-Dk}/\kappa.
\end{split}
\end{equation}
Now choose $\rho>0$ so that
\begin{equation}\label{eq:corridor-coordinate-step}
(R+m+1)\rho<e/10,
\end{equation}
and obtain the coordinates and a common $p'\in[\pc/2,\pc)$ from
Proposition~\ref{prop:moves}, with edge increments at most $\rho$.
Thus $m$ is fixed before the trial count and collar width; both are
fixed before the coordinate scale and the parameter $p'$.
At site $v$ put
\[
M_v=\{0\le t-c_v^{(1)}\le\rho,\
|z-c_v^{(2)}|\le B\}.
\]
In a corridor $v,x$ of sign $\sigma$, use the successive input regions
$B_0=M_v$ and, for $1\le i\le L$,
\begin{equation}\label{eq:relay-regions}
B_i=\{|t-c_v^{(1)}-i|\le(i+1)e,\
|z-c_v^{(2)}-\sigma\mu i|\le b_i\},
\qquad b_i=\max(2,B-i/2).
\end{equation}
The last target is $B_{L+1}=M_x$.
Each distance-$R$ collar of $B_i$, $0\le i\le L$, is contained in
$D_{vx}$. From every vertex $y$ in that collar, one of the two seed
moves reaches the next region with probability at least $1-\eta_0$,
using paths in $D_{vx}$. We give the estimates, including the last
crossing. Suppose first that $0\le i<L$ and that $y$ is in the
collar of $B_i$. A distance-$R$ displacement changes either coordinate
by at most $R\rho$. Write
$r=z(y)-c_v^{(2)}-\sigma\mu i$ for the vertical error at the current
integer time. Choose a move sign $\tau\in\{-1,1\}$ with $\tau r\le0$,
either sign when $r=0$. Its target error relative to the next axis
point is $r+\tau-\sigma\mu$, up to $e/4$. With $b_0=B$, its magnitude
is at most
\[
\max(1+\mu,b_i+R\rho-1+\mu)+e/4\le b_{i+1}.
\]
The inequality follows from $\mu=1/4$, $b_i\ge2$, and
$R\rho+e/4<1/4$. Time error increases by at most $R\rho+e/4<e$;
at $i=0$ the additional initial interval length $\rho$ also fits
the allowed $2e$.
Since $b_L=2$, a move from the collar of $B_L$ starts below time $T$
and ends above it. The starting vertex may be anywhere in $B(y,m)$,
so its additional time error is $m\rho$, paid for by
\eqref{eq:corridor-coordinate-step}. Along the path, the first vertex
at or above $T$ has time in $[T,T+\rho]$. Its height differs from
the child center by at most $2+R\rho+C+\mu/2<B$, so it lies in $M_x$.
For every move, while its time is between the endpoint times, its
deviation from the tube axis is at most
\[
B+R\rho+C+\mu\bigl((L+1)e+\rho+R\rho+C\bigr)<H.
\]
Outside that time interval its time is within $C+1$ of an endpoint
and its height lies in that endpoint's $Q$. This proves containment
of the paths. Collar containment follows from the same estimates
without the $C$ terms. The induced corridor therefore contains every
original edge of each indicated path, as required for the seed-move
probability to hold inside the corridor.
\input{figures/corridors}
\subsection{A transfer estimate in a fresh collar}
The exterior-contact, independent-seed, and shell-conditioned target
construction adapts Kozma and Nitzan's Lemma~10
\cite[Section~4]{KozmaNitzan2024}. We prove the version needed for fresh
metric collars in the original graph, using Theorem~\ref{thm:joint-gluing}.
The next argument applies to a countable product graph consisting of
original edges of $G$ and one synthetic source $*$ wired to finitely
many vertices. Edges outside the designated fresh region may have
arbitrary independent probabilities, including zero and one.
\begin{proposition}[Fresh-collar transfer]\label{prop:transfer}
Let $G$ and the parameters $m,k,R,K,\eta_0,\lambda,\kappa,p'$ satisfy
the choices in Subsection~\ref{subsec:corridor-scales}. Consider a
countable product graph whose edges are original edges of $G$,
together with a synthetic source $*$ joined by deterministic open
edges to finitely many vertices. Original edges have arbitrary
independent probabilities except where specified below.
Let $T_*$ be a fixed vertex set in this product graph.
Let $B_*$ be a vertex set whose distance-$R$ collar is contained in a
subgraph $D_*$ having all its induced original edges present and iid
with probability $p'$. Suppose each vertex $y$ in the collar satisfies
\[
\PP_{p'}(B(y,m)\leftrightarrow T_*\text{ by paths in }D_*)
\ge1-\eta_0.
\]
Suppose the wired seed vertices are outside the collar, and all other
edges of the product graph are original edges of $G$. Then
\begin{equation}\label{eq:fresh-collar-transfer}
\PP(*\leftrightarrow B_*,\ *\nleftrightarrow T_*)\le\kappa.
\end{equation}
In particular this applies to each successive pair in
\eqref{eq:relay-regions}, whenever the whole corridor is fresh and
the wires are outside the input collar.
\end{proposition}
\begin{proof}
The empty input is immediate. We first choose a shell at which there
are unlikely to be only a few exterior contacts. We will use the
contacts to reach a relay set determined by independent interior bits,
then apply joint gluing after those bits have been fixed.
\paragraph{A shell with enough contacts.}
Use distance in the original graph to
$B_*$. For $m+1\le j\le R$, let $X_j$ be the level-$j$ vertices
reachable from $*$ using only vertices at levels at least $j$ and
the wired source. It is measurable in the exterior bits with both
endpoints at these levels. Hitting $B_*$ requires $X_j\ne\varnothing$.
If $1\le|X_j|<k$, closing all edges from $X_j$ to level $j-1$
has conditional probability at least $(1-\pc)^{Dk}$ and forces the
minimum reached level to be exactly $j$. These minimum-level events
are disjoint for different $j$. Thus some deterministic $j$ satisfies
\begin{equation}\label{eq:few-contacts}
\PP(1\le|X_j|<k)
\le\frac{(1-\pc)^{-Dk}}{R-m}<\kappa/4.
\end{equation}
The edges closed here are fresh collar edges, independent of the
exterior. Distance changes by at most one along every original edge;
the source wires lie outside all these levels.
Fix this deterministic $j$. Let $\mathcal F_{\rm ext}$ be the
sigma-field generated by edges with both endpoints at levels at least
$j$. It determines $X_j$ and will determine the finite list of contacts
used for trials.
\paragraph{An interior relay set.}
For every level-$j$ vertex $v$, fix an inward geodesic of length
$m+1$ ending at $y_v$, and a spanning tree of $B(y_v,m)$. The geodesic
and tree lie in the collar, and every one of their edges has an
endpoint of level less than $j$. Let $W_v$ be the event that all
these trial edges are open. Its probability satisfies
\[
s_v:=\PP(W_v)\ge s_0:=(\pc/2)^{m+1+V_+(m)}.
\]
Let $\xi$ be the configuration on the union of all these fixed trial
edge sets, including trials at vertices not ultimately selected.
These are fresh product bits, independent of $\mathcal F_{\rm ext}$.
Define
\[
g_v(\xi)=\PP(B(y_v,m)\leftrightarrow T_*\mid\xi).
\]
This conditional probability integrates over \emph{all} remaining
bits, including those generating $\mathcal F_{\rm ext}$. The actual
exterior chooses contacts but is not fixed in this target probability.
The function $g_v$ is increasing in $\xi$ and has
mean at least $1-\eta_0$. Harris's inequality and Markov's inequality
therefore give
\begin{equation}\label{eq:good-trial}
\PP(W_v,\ g_v<1-\lambda)\le s_v\eta_0/\lambda.
\end{equation}
Define the relay set before choosing the contact list:
\[
A(\xi)=\{v:\ d(v,B_*)=j,\ W_v\text{ occurs},\ g_v(\xi)\ge1-\lambda\}.
\]
This set contains every good trial vertex and depends only on $\xi$.
Given $\xi$, each $v\in A(\xi)$ is connected by its trial edges to
the whole seed ball, so its conditional probability of reaching $T_*$
is at least $1-\lambda$. The remaining law is a countable product
with the trial states fixed. Corollary~\ref{cor:gluing-failure} gives
\begin{equation*}
\PP(*\leftrightarrow A(\xi),\ *\nleftrightarrow T_*\mid\xi)
\le\lambda.
\end{equation*}
It remains to bound the probability that the source hits $B_*$
without reaching this relay set.
\paragraph{Reaching an interior relay from the exterior.}
Fix an enumeration of the countable vertex set. If $|X_j|\ge k$,
select its first available vertices in this order, using only the
exterior, at pairwise distances greater than $4m+2$, until
the sum of their $s_v$ is in $[K,K+1]$. Greedy selection deletes at
most $V_+(4m+2)$ candidates each time, so
\eqref{eq:corridor-trial-scales} guarantees this is possible; the
selected list is finite even when $X_j$ is infinite. Each trial lies
within distance $2m+1$ of its vertex, so the selected trials have
disjoint edge sets. Conditional on the exterior, their probability
of no success is at most $e^{-K}=\kappa/4$. By
\eqref{eq:good-trial} their probability of a successful trial with
$g_v<1-\lambda$ is at most
$(K+1)\eta_0/\lambda\le\kappa/4$. These estimates remain valid
after selection because the entire $\xi$ law is independent of
the exterior selecting the list.
On a hit of $B_*$, the contact set is nonempty. Outside the small-contact
error in \eqref{eq:few-contacts} and the two trial errors, some selected
exterior contact belongs to $A(\xi)$ and is already connected to the
source. Thus the probability of hitting $B_*$ without hitting $A(\xi)$
is at most $3\kappa/4$. Integrating the conditional gluing bound and
using $\lambda=\kappa/4$ proves \eqref{eq:fresh-collar-transfer}.
\end{proof}
\subsection{Adaptive exploration with stored predictions}
Stored high conditional probabilities are used in the proof of
Kozma and Nitzan's Theorem~6, particularly equations~(30)--(32)
\cite{KozmaNitzan2024}. The adaptive block strategy has an earlier
antecedent in Grimmett and Marstrand \cite[Sections~3--4]{GrimmettMarstrand1990}.
Here we use an oriented quadrant, choose one incoming corridor,
reveal whole edge domains, and prove the conditional-failure boundary
estimate explicitly.
\begin{proposition}[Subcritical exploration]\label{prop:exploration}
Suppose the coordinates and seed radius satisfy
Proposition~\ref{prop:moves}, the corridor layout satisfies
Lemma~\ref{lem:corridors}, and every relay in
\eqref{eq:relay-regions} satisfies Proposition~\ref{prop:transfer}.
If
\[
2(\eta_0+L\kappa)<\delta,\qquad
\delta+2(L+1)\kappa/\delta\le\varepsilon,
\qquad\sum_{l\ge1}4^l\varepsilon^{l/4}<1,
\]
then Bernoulli bond percolation at $p'$ has an infinite cluster with
positive probability. In particular, the choices
\eqref{eq:corridor-trial-scales}--\eqref{eq:corridor-coordinate-step}
and the preceding error parameters have this consequence at $p'<\pc$.
\end{proposition}
\begin{proof}
Choose $o$ with $(t(o),z(o))=(0,0)$, and wire a synthetic source to
the finite ball $B(o,m)$. A revealed history
records a union of the edge domains $\mathcal Q_v,\mathcal E_{vx}$
and their actual $p'$ states. In a prospective graph obtained by adding
another edge domain, previously revealed states remain fixed and the
other edges have their conditional product law. We include only the
edges of those domains, even if further original edges join vertices
already present. The domains may be infinite; the conditional-law
justification below covers this point.
\paragraph{Initialization.}
At the root site, the two moves reach the corresponding $B_1$ directly
with probability at least $1-\eta_0$. From $B_1$ onward, source wires
are outside each input collar, by their time separation and
\eqref{eq:corridor-coordinate-step}. Summing
Proposition~\ref{prop:transfer} in a fixed child corridor shows that
the source misses its child mark with probability at most
$\eta_0+L\kappa$. Reveal $\mathcal Q_0$. The two conditional
predictions for reaching the child marks are both at least
$1-\delta$ on an event of positive probability: the probability
that either fails this threshold is at most
$2(\eta_0+L\kappa)/\delta<1$. Condition on this
$\mathcal Q_0$-measurable event, declare the root good, and store
these two predictions. The source already hits $M_0$ through $o$.
For the rest of the proof, probabilities refer to the law conditioned
on this initialization event.
\paragraph{A test and its two exposure times.}
Process sites by increasing layer $a+b$, in a fixed order within
each layer. A nonroot site is tested if it has a good parent; choose
one such parent $w$ deterministically. Sites with no good parent are
not tested. Before testing $v$, let $I$ denote the revealed history.
There are two geometric facts at this time. The incoming corridor
$\mathcal E_{wv}$ meets $I$ only in its parent's already known
$\mathcal Q_w$. Every outgoing corridor $\mathcal E_{vx}$ misses $I$
entirely. Indeed, no revealed corridor has endpoint $v$ or either child
of $v$: earlier tests reveal only their own incoming corridors, and
all sites of a preceding layer are processed first. Apply
Lemma~\ref{lem:corridors} to these domains and to $\mathcal Q_0$.
The first fact preserves the prediction stored when $w$ became good.
Intervening reveals meet $\mathcal E_{wv}$ only in $\mathcal Q_w$,
which was already known then, so they leave the other incoming bits
independent with parameter $p'$. The newly included history edges can
only add paths. Thus, in the prospective graph $I\cup\mathcal E_{wv}$,
\begin{equation}\label{eq:stored-prediction}
\PP(A_v\mid I)\ge1-\delta,
\qquad A_v=\{*\leftrightarrow M_v\text{ in }I\cup\mathcal E_{wv}\}.
\end{equation}
The second fact allows us to estimate both outgoing predictions
\emph{before} revealing the incoming corridor. For a child $x$ of $v$,
use the prospective graph
\[
I\cup\mathcal E_{wv}\cup\mathcal E_{vx}.
\]
Conditionally on $I$, every edge of $D_{vx}$ still has its fresh iid
$p'$ law. In particular this includes the shared endpoint region
$\mathcal Q_v=\mathcal E_{wv}\cap\mathcal E_{vx}$, which has not yet
been revealed. The source wires lie outside all the input collars,
by time separation. Apply Proposition~\ref{prop:transfer} to the
$L+1$ consecutive relays, all in this same prospective graph. It gives
\begin{equation}\label{eq:prospective-transfer}
\PP(A_v,\ *\nleftrightarrow M_x\mid I)\le(L+1)\kappa.
\end{equation}
A hit of the first region and a miss of the last entails a hit
followed by a miss at some consecutive pair, so no independence
between the successive estimates is needed.
Now reveal all of $\mathcal E_{wv}$ and call the enlarged history
$F$. The event $A_v$ and every state in $\mathcal Q_v$ are now known.
The outgoing edges outside $\mathcal Q_v$ remain unexposed. For each
child compute
\[
q_x(F)=\PP(*\leftrightarrow M_x\text{ in }F\cup\mathcal E_{vx}\mid F).
\]
This product integral fixes the incoming states and integrates over
the unexposed outgoing edges; computing it reveals no further edge.
Declare $v$ good if $A_v$ occurs and both predictions are at least
$1-\delta$; otherwise declare the tested site failed. In the good
case store both predictions. By conditioning
\eqref{eq:prospective-transfer} on $F$,
\[
\EE[\mathbf1_{A_v}(1-q_x(F))\mid I]\le(L+1)\kappa.
\]
Together with \eqref{eq:stored-prediction} and Markov's inequality,
this gives the uniform conditional failure bound
\begin{equation}\label{eq:conditional-test-failure}
\PP(v\text{ fails}\mid I)
\le\delta+\frac{2(L+1)\kappa}{\delta}
\le\varepsilon.
\end{equation}
\paragraph{Conditional laws for countable reveal domains.}
We justify the product-law statements also for infinite reveal
domains. At any finite slot there are only finitely many earlier
decisions and parent choices. For each possible decision sequence,
the union $R$ of revealed edge sets is deterministic, and the event
of following that sequence is measurable in the coordinates of $R$.
The sequence, its edge states, and every prediction are functions
of those coordinates; a prediction is a measurable product integral
on the countable complement. On this part of the history space,
independence of disjoint coordinate sets gives the original product
law on $R^c$, conditionally on the full revealed states. This is a
statement about conditional kernels, and does not condition on a
positive-probability individual infinite configuration. It follows
either directly by Fubini on the two countable coordinate sets or by
first testing cylinder functions on $R^c$ and then using a monotone
class argument. The initial conditioning is measurable in
$\mathcal Q_0$ and hence preserves this property. This proves the
induction on slots. In particular, future corridor bits are not
revealed by decisions based on their conditional probabilities.
\paragraph{A boundary of failed sites.}
For any fixed finite set $S$ of nonroot sites,
\begin{equation}\label{eq:specified-failures}
\PP(\text{every site of }S\text{ is tested and fails})
\le\varepsilon^{|S|}.
\end{equation}
Indeed, enumerate the finite slots up to the last site of $S$.
At its slot, the event that a given site is tested and that the
previous specified sites failed is measurable before the test.
Apply \eqref{eq:conditional-test-failure} and iterate. A specified
site that is not tested makes the event impossible. A set containing
the good root also has probability zero.
If the good set is finite, draw the counterclockwise boundaries of
its unit site squares and cancel oppositely oriented shared edges.
The remaining directed graph is finite and balanced, so its edges
decompose into closed directed trails with no repeated edge. One
trail contains the fixed west edge of the root square, since the
sites lie in the nonnegative quadrant. In a trail of length $l$,
half the steps point up or left, by horizontal and vertical balance.
An up step crosses an east adjacency from a good site to a nongood
child; a left step crosses a north adjacency of the same kind.
Every such child was tested and failed, because all its parents were
processed earlier. Each child has at most two parents, so this trail
specifies at least $l/4$ distinct failed sites.
There are at most $4^l$ trails of length $l$ starting with the fixed
oriented root edge. For each candidate, its up and left edges
determine the outside child sites; restricting to edge-distinct
trails preserves the preceding multiplicity bound. Equation
\eqref{eq:specified-failures} and a union bound show that the
probability of a finite good set is at most the sum in
\eqref{eq:directed-contour-series}, which is less than one.
Thus with positive conditional probability there are infinitely
many good sites. Their layers, hence their time coordinates, are
unbounded. Each good mark was reached by an actual open path from
the wired finite seed at its test, and later reveals do not change
those states. The seed therefore has an infinite open component.
Removing the synthetic source leaves an infinite cluster from one
of its finitely many wired vertices. The initialization event had
positive probability, so this conclusion also has positive
probability in the unconditioned $p'$ law.
Finally, the chosen parameters satisfy the two numerical hypotheses.
They give $\eta_0\le\kappa$ and
\[
2(\eta_0+L\kappa)\le2(L+1)\kappa
=\varepsilon\delta/4<\delta,
\qquad
\delta+2(L+1)\kappa/\delta=\varepsilon/2\le\varepsilon.
\]
The remaining hypothesis is exactly
\eqref{eq:directed-contour-series}.
\end{proof}
Since $p'<\pc$, Proposition~\ref{prop:exploration} contradicts the
assumed critical jump and completes the induction in
Theorem~\ref{thm:structured}.
==== END No-percolation-at-criticality-on-quasi-transitive-graphs//corridor-exploration.tex ====
==== BEGIN No-percolation-at-criticality-on-quasi-transitive-graphs//corridors.tex ====
\begin{figure}[htbp]
\centering
\begin{tikzpicture}[x=.9cm,y=.9cm,>=Stealth]
\foreach \ax/\ay/\bx/\by in {0/0/5/2.5,0/0/5/-2.5,5/2.5/10/0,5/-2.5/10/0}{
\filldraw[fill=blue!8,draw=blue!45!black,line width=.5pt]
(\ax,{\ay+.2})--(\bx,{\by+.2})--(\bx,{\by-.2})--(\ax,{\ay-.2})--cycle;
\draw[->,blue!55!black,line width=.7pt,shorten <=9pt,shorten >=9pt]
(\ax,\ay)--(\bx,\by);
}
\foreach \ax/\ay in {0/0,5/2.5,5/-2.5,10/0}{
\filldraw[fill=orange!10,draw=orange!65!black]
({\ax-.42},{\ay-.52}) rectangle ({\ax+.42},{\ay+.52});
\filldraw[fill=green!30!black,draw=green!30!black]
(\ax,{\ay-.3}) rectangle ({\ax+.04},{\ay+.3});
}
\node[left=7pt] at (-.42,0) {$Q_{(0,0)}$};
\node[above=6pt] at (5,3.02) {$Q_{(1,0)}$};
\node[below=6pt] at (5,-3.02) {$Q_{(0,1)}$};
\node[right=7pt] at (10.42,0) {$Q_{(1,1)}$};
\node[above=4pt,rotate=26.565] at (2.5,1.48) {$D_{(0,0),(1,0)}$};
\draw[->,black!65] (7,-2.15)--(9.97,-.28);
\node[below,align=center] at (7,-2.18) {mark $M_{(1,1)}$};
\end{tikzpicture}
\caption{A diamond in the corridor layout. Corridors intersect only
inside the rectangle at a shared endpoint. The narrow green regions
are the marks $M_v$. Revealing an incoming corridor reveals the
endpoint rectangle, while the parts of the outgoing corridors outside
that rectangle remain fresh. Widths and the two coordinate scales are exaggerated;
the separation inequalities are proved in Lemma~\ref{lem:corridors}.}
\label{fig:corridors}
\end{figure}
==== END No-percolation-at-criticality-on-quasi-transitive-graphs//corridors.tex ====
==== BEGIN No-percolation-at-criticality-on-quasi-transitive-graphs//gluing.tex ====
\section{A joint gluing inequality}
\label{sec:gluing}
The geometric construction will reach a set of possible relay vertices and
then need to continue to a target. The vertex reached is selected by the
same edge configuration that must supply the continuation, so its
connection probability cannot simply be treated as an independent factor.
We prove an inequality that controls this dependence uniformly in the
number of relays.
Connections in this section are witnessed by finite open paths, including
paths of length zero. For an undirected graph $G$ with independent edge
states, write $C^G(x)$ for the vertex cluster of $x$, and put
$C^G(S)=\bigcup_{x\in S}C^G(x)$. Superscripts are omitted when the graph
is clear. Vertex deletion retains the original probabilities on all
remaining edges. Parallel edges are allowed; loops can be discarded.
\begin{theorem}[Joint gluing]
\label{thm:joint-gluing}
Let $G$ have countably many vertices and edges, with independent edge-open
probabilities in $[0,1]$. For a vertex $o$, a nonempty set $A$ of vertices,
and any set $T$ of vertices,
\begin{equation}
\label{eq:joint-gluing}
\mathbb P(o\leftrightarrow A,\ o\leftrightarrow T)
\ge \mathbb P(o\leftrightarrow A)
\inf_{a\in A}\mathbb P(a\leftrightarrow T).
\end{equation}
For finite $A$, the infimum is a minimum.
\end{theorem}
Taking $T=\{b\}$ and enlarging the event on the left proves the
multiplicative gluing inequality of Kozma and Nitzan,
Conjecture~1 of \cite{KozmaNitzan2024}. The finite statement also follows
from the first-contact comparison (GEN) in \cite[Section~3.4]{Leder2026},
as recorded in \cite{ConnectionInequalities2026}. We give a direct proof,
then pass to countable graphs.
For the finite proof, with $o\notin A$, we will construct numbers
$\alpha_a\ge0$, $a\in A$, whose sum is $\mathbb P(o\leftrightarrow A)$
and for which
\[
\mathbb P(o\leftrightarrow A,\ o\leftrightarrow T)
\ge \sum_{a\in A}\alpha_a\mathbb P(a\leftrightarrow T).
\]
Bounding the sum by its total mass times the least target probability
will prove the theorem. The weights come from the inverse of a triangular
matrix of conditional cluster probabilities. A positivity property of
its cluster columns will give both the required signs in the inverse
and the displayed comparison. Related coefficient
questions appear in \cite[Section~5.2]{KozmaNitzan2024}, where the system
uses a symmetric matrix of joint connection probabilities instead.
\subsection{Conditional cluster columns}
Throughout the finite-graph proof assume $p_e<1$ for every edge; zero
probabilities are permitted. If $C(S)=w$ has positive probability, its
occurrence is determined by edges having an endpoint in $w$: all vertices
of $w$ must connect to $S$ within $w$, and all edges from $w$ to its
complement must be closed. Thus edges induced outside $w$ retain their
independent original laws. The same observation applies inside a graph
obtained by vertex deletion. For $S=\varnothing$, its cluster is empty.
Choose distinct distinguished vertices $x_1,\ldots,x_N$.
They need not exhaust the vertices of $G$; all other vertices and their
edges remain in the graph. For $1\le k\le N$, put
\[
S_k=\{x_1,\ldots,x_{k-1}\},\qquad
E_k=\{C(x_k)\cap S_k=\varnothing\},\qquad d_k=\mathbb P(E_k)>0.
\]
The positivity follows by closing every edge incident to $x_k$.
Let $\mu_k$ be the law of $C(x_k)$ conditional on $E_k$, and set
\[
\mathcal D_k=\{U\subseteq V(G):x_k\in U,\ U\cap S_k=\varnothing\}.
\]
For $F:\mathcal D_k\to[0,\infty)$, define vectors in $\mathbb R^N$ by
\[
v_k^F(i)=\mathbb E_{\mu_k}
[\mathbf1_{\{x_i\in C(x_k)\}}F(C(x_k))],
\qquad h_k=v_k^1.
\]
The matrix $H=(h_1\ \cdots\ h_N)$ is unit lower triangular.
The vector $v_k^F-(\mathbb E_{\mu_k}F)h_k$ records the conditional
covariances of $F(C(x_k))$ with the distinguished-vertex indicators.
For increasing $F$, we will show that this vector is a nonnegative
combination of later columns.
The following deletion estimate supplies the nonnegative terms in that
combination.
\subsection{The deletion estimate and column positivity}
\begin{lemma}[Deleted-set residual]
\label{lem:deleted-residual}
Fix a finite product graph $G$, a vertex $s$, a vertex set $S$ not
containing $s$, and an increasing function $F$ on sets that contain $s$
and avoid $S$. For $w\supseteq S$ with $s\notin w$, define
\[
c(w)=\mathbb E^{G\setminus w}F(C(s)).
\]
For $U\subseteq V(G)\setminus(S\cup\{s\})$, sample
$W_U=C^{G\setminus U}(S)$ and define
\[
R_F(U)=\mathbb E\left[
\mathbf1_{\{s\notin W_U\}}
\bigl(c(W_U)-c(W_U\cup U)\bigr)\right],
\]
where the integrand is zero when $s\in W_U$. Then $R_F$ is nonnegative
and increasing under inclusion of $U$.
\end{lemma}
\begin{proof}
Sample all edges of $G$ once and use their restrictions for every graph
below. Conditional on an exact value $W_U=w$, the edges induced outside
$w$ have product law, including those involving the previously deleted
vertices $U$. Consequently $R_F(U)$ is the expectation of
\[
D_U=\mathbf1_{\{s\notin W_U\}}
\left[F\bigl(C^{G\setminus W_U}(s)\bigr)
-F\bigl(C^{G\setminus(W_U\cup U)}(s)\bigr)\right]
\]
in this common configuration. This quantity is nonnegative.
If $U\subseteq U'$, then $W_{U'}\subseteq W_U$. On
$\{s\notin W_U\}$, the first cluster in $D_U$ grows when $U$ is replaced
by $U'$. The second cluster is exactly $C^{G\setminus U}(s)$: in
$G\setminus U$ the cluster of $s$ is disjoint from the union of the
$S$-clusters. The corresponding second cluster for $U'$ is
$C^{G\setminus U'}(s)$ and can only shrink. Increasingness of $F$
therefore gives $D_{U'}\ge D_U$ on this event. On its complement,
$D_U=0$ and $D_{U'}\ge0$. Taking expectations proves the claim.
\end{proof}
\begin{lemma}[Cluster-column positivity]
\label{lem:cluster-column}
For every nonnegative increasing $F$ on $\mathcal D_k$,
\begin{equation}
\label{eq:cluster-column}
v_k^F-(\mathbb E_{\mu_k}F)h_k
\in\left\{\sum_{l>k}a_lh_l:a_l\ge0\right\}.
\end{equation}
In particular $H^{-1}v_k^F$ has nonnegative coordinates.
\end{lemma}
\begin{proof}
We induct downward in $k$. At a fixed index, exposing the earlier
clusters will split $v_k^F$ into an averaged version of itself and
nonnegative contributions from later columns. Repeating the averaging
will replace $F$ by its mean and leave exactly the difference in
\eqref{eq:cluster-column}.
For $k=N$, both vectors in the difference have only their $N$th
coordinate nonzero, so the difference vanishes. Fix $k<N$ and assume
the claim for all larger indices. Write
$s=x_k$, $S=S_k$, $W=C(S)$, and
$c(w)=\mathbb E^{G\setminus w}F(C(s))$ for $w\supseteq S$ avoiding $s$.
The function $c$ is nonincreasing in $w$ by restriction coupling.
Condition on $W=w$ and $s\notin w$, and use the independent product
law outside $w$. If $x_i\notin w$, partition its cluster by its earliest
distinguished vertex. This is $x_k$ exactly when $x_i\in C(s)$;
write $L_{il}^w$ for the case where it is $x_l$, $l>k$.
Conditional on the exact cluster $U=C^{G\setminus w}(x_l)$ in the latter
case, the expected value of $F(C(s))$ is $c(w\cup U)$.
Partitioning the expectation $c(w)$ in this way yields
\begin{equation}
\label{eq:cluster-partition}
\begin{split}
\mathbb E^{G\setminus w}
[\mathbf1_{\{x_i\in C(s)\}}F(C(s))]
&=c(w)\mathbb P^{G\setminus w}(x_i\in C(s))\\
&\quad+\sum_{\substack{l>k\\x_l\notin w}}\mathbb E^{G\setminus w}
[\mathbf1_{L_{il}^w}\{c(w)-c(w\cup C(x_l))\}].
\end{split}
\end{equation}
If $x_i\in w$, every term is zero instead.
We first average the leading term in \eqref{eq:cluster-partition}.
Given $C(s)=U$ under $E_k$, the earlier-root cluster $W$ has the law of
$W_U=C^{G\setminus U}(S)$, by the product law outside the exposed
cluster. Define
\[
(PF)(U)=\mathbb E[c(W_U)],\qquad U\in\mathcal D_k.
\]
This function is nonnegative and increasing, since $W_U$ shrinks with
$U$ and $c$ decreases with its argument. Conditioning first on $W$ and
then on $C(s)$ shows that the averaged leading term is
\[
\mathbb E[\mathbf1_{\{x_i\in C(s)\}}c(W)\mid E_k]
=\mathbb E_{\mu_k}[\mathbf1_{\{x_i\in C(s)\}}(PF)(C(s))]
=v_k^{PF}(i).
\]
The remaining terms give later columns. More precisely, averaging
\eqref{eq:cluster-partition} conditional on $E_k$ gives
\begin{equation}
\label{eq:column-decomposition}
v_k^F=v_k^{PF}+\sum_{l>k}v_l^{F_l},\qquad
F_l(U)=\frac{d_l}{d_k}R_F(U),\quad U\in\mathcal D_l.
\end{equation}
Here the residual uses the fixed roots $s,S$ of this induction step.
To check the normalization, on $E_k$ the event $L_{il}^W$ is exactly
$E_l\cap\{x_i\in C(x_l)\}$. Given $C(x_l)=U$ under $E_l$, the
$S$-cluster is $W_U$ with product law in $G\setminus U$, and the remaining
condition $E_k$ is $s\notin W_U$. Division by $d_k$ and conditioning
on $E_l$ give precisely the factor $d_l/d_k$.
Lemma~\ref{lem:deleted-residual} shows that every $F_l$ is nonnegative
and increasing. The induction hypothesis therefore places every term
$v_l^{F_l}$ in the cone generated by $h_j$ with $j>k$.
Thus one application of $P$ leaves a remainder in the cone of later
columns. To iterate this decomposition, we identify the limit of $P^jF$.
The operator $P$ first samples $W$ conditional on $C(s)$ and then samples
$C(s)$ conditional on $W$. Both are conditional laws of the joint
distribution given $E_k$, so $\mu_k$ is stationary for this two-step
Markov chain. These alternating cluster updates are the method of
van den Berg, H\"aggstr\"om and
Kahn~\cite[Section~2.1]{VanDenBergHaggstromKahn2006}.
Every transition puts mass at least
\[
a=\prod_{e\ni s}(1-p_e)>0
\]
on $\{s\}$. Subtracting this common mass from two transition averages
shows $\operatorname{osc}(Pg)\le(1-a)\operatorname{osc}(g)$ for every
function on the finite state space. Stationarity then implies
$P^jF\to\mathbb E_{\mu_k}F$ uniformly.
Iterate \eqref{eq:column-decomposition}. Each $P^jF$ remains
nonnegative and increasing, so $v_k^F-v_k^{P^jF}$ belongs to the cone
generated by the later columns. This cone is closed: on coordinates
$k+1,\ldots,N$ its generators form a unit lower-triangular basis.
Taking the limit proves \eqref{eq:cluster-column}. Finally
$H^{-1}h_l$ is the $l$th coordinate vector, proving the last assertion.
\end{proof}
\subsection{Nonnegative relay weights}
Apply Lemma~\ref{lem:cluster-column} to
\[
F(U)=\mathbf1_{\{U\cap\{x_{k+1},\ldots,x_N\}\ne\varnothing\}}.
\]
Its mean $m_k$ under $\mu_k$ is less than one, since $x_k$ can be
isolated. The centered vector is $(1-m_k)(h_k-e_k)$, where $e_k$
is the $k$th coordinate vector. Hence there are numbers
$\Gamma_{lk}\ge0$, $l>k$, such that
\[
h_k=e_k+\sum_{l>k}\Gamma_{lk}h_l.
\]
Let $\Gamma$ be zero on and above the diagonal. In matrix form,
$H=I+H\Gamma$, and therefore
\begin{equation}
\label{eq:cluster-inverse}
H^{-1}=I-\Gamma.
\end{equation}
Moreover, partitioning the cluster of $x_i$ by its first distinguished
vertex gives
\begin{equation}
\label{eq:cluster-row-mass}
Hd=\mathbf1,\qquad (I-\Gamma)\mathbf1=d,
\qquad d=(d_1,\ldots,d_N)^{\mathsf T}.
\end{equation}
\begin{proof}[Proof of Theorem~\ref{thm:joint-gluing}]
First suppose the graph is finite and all $p_e<1$.
If $o\in A$, the left side of \eqref{eq:joint-gluing} equals
$\mathbb P(o\leftrightarrow T)$ and the inequality is immediate.
Otherwise take the distinguished list to consist of the vertices of
$A$ followed by $x_N=o$, and set
\[
F(U)=\mathbf1_{\{U\cap A\ne\varnothing,\ U\cap T\ne\varnothing\}},
\qquad y_i=\mathbb E F(C(x_i)).
\]
This is one nonnegative increasing function, restricted to each
$\mathcal D_k$ as needed. Partitioning by the first distinguished
vertex gives $y=\sum_k d_kv_k^F$, so
Lemma~\ref{lem:cluster-column} implies $H^{-1}y\ge0$ coordinatewise.
The last row of \eqref{eq:cluster-inverse} yields
\[
y_N\ge\sum_{i<N}\Gamma_{Ni}y_i.
\]
For $i<N$, length-zero paths give $y_i=\mathbb P(x_i\leftrightarrow T)$,
whereas $y_N$ is the joint probability in the theorem. By
\eqref{eq:cluster-row-mass},
\[
\sum_{i<N}\Gamma_{Ni}=1-d_N=\mathbb P(o\leftrightarrow A).
\]
Thus the promised relay weights are $\alpha_{x_i}=\Gamma_{Ni}$ for $i<N$.
They are nonnegative, proving the finite-graph inequality.
This argument also covers $T=\varnothing$, when $F=0$.
All event probabilities on a finite graph are polynomials in the edge
probabilities. Approximating each probability equal to one from below
therefore includes deterministic open edges as well as closed ones.
For a countable graph and finite $A$, exhaust the graph by finite
subgraphs containing $o$ and $A$, and intersect $T$ with their vertex
sets. Every connection has a finite witness, so the individual and
joint connection events increase to the corresponding events in $G$.
The minimum over the finite set $A$ also converges. This proves
\eqref{eq:joint-gluing} for finite $A$. Finally exhaust a countable
nonempty $A$ by finite nonempty sets $A_j$. The two events involving
$A_j$ increase to those involving $A$, while
$\min_{a\in A_j}\mathbb P(a\leftrightarrow T)$ decreases to the infimum
over $A$. Taking limits proves the result.
\end{proof}
\begin{corollary}[Failure after reaching a relay]
\label{cor:gluing-failure}
In the setting of Theorem~\ref{thm:joint-gluing}, let $0\le\lambda\le1$.
If $\mathbb P(a\leftrightarrow T)\ge1-\lambda$ for every $a\in A$, then
\[
\mathbb P(o\leftrightarrow A,\ o\not\leftrightarrow T)
\le\lambda\,\mathbb P(o\leftrightarrow A)\le\lambda.
\]
The same conclusion holds for $A=\varnothing$.
\end{corollary}
\begin{proof}
Subtract \eqref{eq:joint-gluing} from $\mathbb P(o\leftrightarrow A)$.
For an empty relay set the event on the left is empty.
\end{proof}
The theorem and corollary may be applied after fixing any collection of
edge states, provided the remaining edges still have product law.
Relay and target sets must then be fixed under that conditioning.
In particular, a later adaptive choice of contacts is not an additional
conditioning to be inserted into their connection probabilities.
We apply this inequality in the corridor construction of
Section~\ref{sec:corridor-exploration}. The remaining sections develop
the geometric argument for graphs satisfying the polynomial bound along
an unbounded sequence of radii, beginning with the quotient action that
will supply the corridor coordinates.
==== END No-percolation-at-criticality-on-quasi-transitive-graphs//gluing.tex ====
==== BEGIN No-percolation-at-criticality-on-quasi-transitive-graphs//interpolation.tex ====
\begin{figure}[tbp]
\centering
\begin{tikzpicture}[x=1cm,y=1cm,
cluster/.style={draw=blue!55!black,fill=blue!5,ellipse,
minimum width=1.12cm,minimum height=.82cm,inner sep=5pt},
contact/.style={draw=blue!65!black,line width=1pt},
closed/.style={draw=black!45,dashed,line width=.6pt}]
\node[cluster] (L) at (-5,0) {$L$};
\node[cluster] (K1) at (-2.8,0) {$K_1$};
\node[cluster] (K3) at (-.6,0) {$K_3$};
\node[cluster] (K4) at (1.9,0) {$K_4$};
\node[cluster] (R) at (4.1,0) {$R$};
\node[cluster,draw=black!40,fill=black!3] (K2) at (-2.8,-1.55) {$K_2$};
\draw[contact] (L)--node[above=3pt] {$f_1$}(K1);
\draw[contact] (K1)--node[above=3pt] {$f_3$}(K3);
\draw[contact] (K4)--node[above=3pt] {$f_4$}(R);
\draw[closed] (K3)--node[above=3pt] {$e$}(K4);
\draw[closed] (K1)--node[right=4pt] {$f_2$}(K2);
\node[below=5pt] at (L.south) {left base};
\node[below=5pt] at (R.south) {right base};
\node[below=5pt,black!65] at (K2.south) {inactive};
\end{tikzpicture}
\caption{The two ancestry chains at the end of interpolation.
Here the terminal path edge $e$ joins $K_3$ to $K_4$.
Only $f_1,f_3,f_4$ are opened. Each terminal cluster joins its own
large base; the two sides remain distinct. The inactive contact
$f_2$ stays closed. Vertices inside each cluster are suppressed.}
\label{fig:interpolation}
\end{figure}
==== END No-percolation-at-criticality-on-quasi-transitive-graphs//interpolation.tex ====
==== BEGIN No-percolation-at-criticality-on-quasi-transitive-graphs//introduction.tex ====
\section{Introduction}
\label{sec:introduction}
Bernoulli bond percolation on an undirected graph $G=(V,E)$ retains
each edge independently with probability $p\in[0,1]$. Retained edges
are called open. The open cluster $C_x$ of a vertex $x$ consists of the
vertices joined to $x$ by finite open paths, including $x$ itself. Write
$x\leftrightarrow A$ when $C_x$ meets a set $A\subseteq V$, and
$x\leftrightarrow y$ when $y\in C_x$. With $\PP_p$ denoting the product
law, the critical probability is
\[
\pc(G)=\inf\{p\in[0,1]:
\PP_p(\text{there is an infinite open cluster})>0\}.
\]
A graph is \emph{quasi-transitive} if its automorphism group has finitely
many orbits on vertices. This includes every vertex-transitive graph
and every Cayley graph of a finitely generated group with a finite
generating set.
The criticality problem asks whether an infinite cluster can first
appear at the threshold itself. Benjamini and Schramm formulated the
general quasi-transitive conjecture in their systematic study of
percolation beyond Euclidean lattices
\cite[Conjecture~4]{BenjaminiSchramm1996}.
\begin{theorem}
\label{thm:main}
Let $G$ be an infinite connected locally finite quasi-transitive
undirected graph. If $\pc(G)<1$, then
\[
\PP_{\pc(G)}(\text{there is an infinite open cluster})=0.
\]
Equivalently, $\PP_{\pc(G)}(|C_x|=\infty)=0$ for every vertex $x$.
\end{theorem}
Theorem~\ref{thm:main} resolves the Benjamini--Schramm criticality
conjecture positively for Bernoulli bond percolation. Its conclusion
concerns all vertex orbits.
The hypothesis $\pc<1$ is necessary: at parameter one every edge is
open, so an infinite connected graph percolates.
In particular, the theorem includes nearest-neighbor bond percolation on
$\Z^d$ for every $d\ge2$; see Corollary~\ref{cor:lattices}.
\subsection{The two subexponential arguments}
For a vertex $x$, let $B(x,r)$ be the graph-distance ball of integer
radius $r$. Put $V_-(r)=\min_x|B(x,r)|$ and
$V_+(r)=\max_x|B(x,r)|$. Quasi-transitivity makes these extrema finite
and compares them up to a bounded shift of $r$. It also implies that
$V_+(r)^{1/r}$ has a limit. A limit greater than one is the exponential
case covered by Hutchcroft. In the other case, the proof divides
according to the following exhaustive alternatives:
\begin{enumerate}[label=(\roman*)]
\item $\log V_-(r)/\log r\to\infty$;
\item $V_-(r)\le r^d$ along an unbounded sequence of radii, for some
fixed finite $d$.
\end{enumerate}
This division requires no classification of intermediate growth.
In case (i), suppose that an infinite cluster occurs at $\pc$.
At a slightly smaller parameter, large finite clusters still occur
with probability bounded away from zero. The volume growth then
places two distinct large clusters within a distance that is small
on the logarithmic scale of their sizes. Repeatedly bisecting a
path between them produces a single adjacent pair. Each bisection
adds at most one cluster and one possible connecting edge. We choose these
edges using the decrease in a search's conditional success
probability, and control the total cost by relative entropy.
Section~\ref{sec:dfs-entropy} establishes the search and entropy
estimates. Sections~\ref{sec:interpolation} and~\ref{sec:superpolynomial} show
that the resulting adjacent pair contradicts the bound in
Proposition~\ref{prop:two-cluster}: across a fixed edge, distinct
clusters each of size at least $s$ occur with probability at most
$Cs^{-1/2}$.
In case (ii), we apply the finitary structure theorem of Tessera and
Tointon \cite[Corollary~2.4]{TesseraTointon2021} to an auxiliary
vertex-transitive graph. Lifting its quotient action to $G$ and
passing to a finite-index subgroup gives a finitely generated
nilpotent quotient and a kernel with finite vertex orbits.
Section~\ref{sec:structure} uses an
induction on the number of infinite cyclic factors in a chosen
series of that group. The one-dimensional case has $\pc=1$.
Otherwise there are two integer coordinates on vertices that change
by a fixed translation under each group element. The induction excludes an infinite open ray whose
two coordinates both remain bounded.
Under the assumed critical percolation, uniqueness and this exclusion
produce two high-probability approximate moves in linearly independent
coordinate directions in Section~\ref{sec:moves}. After rescaling, the moves advance by
$(1,1)$ and $(1,-1)$, with arbitrarily small edge steps.
They persist at a parameter below $\pc$. In
Section~\ref{sec:corridor-exploration}, we place corridors in
these coordinates, with intersections confined to their common
end regions. The joint gluing inequality
(Theorem~\ref{thm:joint-gluing}) transfers connections through each
fresh corridor: reaching a relay set whose vertices have uniformly
high target probabilities gives a high conditional chance of continuing
to the target. Finally an adaptive exploration keeps the
conditional chance of failure small at every tested site. A planar
boundary count gives positive probability of infinitely many
successful sites, hence an infinite open cluster below $\pc$.
All paths and all revealed edges belong to $G$; the quotient supplies
coordinates for this construction.
\subsection{History and related methods}
Percolation was introduced by Broadbent and Hammersley
\cite{BroadbentHammersley1957}. For nearest-neighbor bond percolation
on $\Z^d$, planar methods established critical nonpercolation in
dimension two \cite{Harris1960,Kesten1980}. The lace expansion gave
the result in sufficiently high dimensions \cite{HaraSlade1990},
and Fitzner and van der Hofstad obtained it for $d\ge11$
\cite{FitznerHofstad2017}. The sharpness theorems of Aizenman--Barsky
and Menshikov describe the subcritical regime
\cite{AizenmanBarsky1987,Menshikov1986}; they do not by themselves
settle the behavior at the threshold.
Beyond lattices, Benjamini, Lyons, Peres, and Schramm proved critical
nonpercolation for nonamenable graphs admitting a unimodular
quasi-transitive action \cite{BLPS1999Critical}. Tim\'ar excluded
infinitely many infinite critical clusters on transitive
nonunimodular graphs \cite{Timar2006Nonunimodular}, leaving the
possibility of a unique infinite cluster. Hutchcroft excluded all
infinite critical clusters on every quasi-transitive graph of
exponential growth \cite[Theorem~1.2]{Hutchcroft2016}; we use that
entire theorem. Hermon and Hutchcroft treated unimodular
quasi-transitive graphs satisfying a uniform stretched-exponential
return-probability bound with exponent greater than $1/2$
\cite[Theorem~1.2]{HermonHutchcroft2021}. The two arguments above
cover the remaining subexponential case.
Our joint gluing theorem also has a finite-graph and lattice history
that is distinct from the general quasi-transitive conclusion.
Kozma and Nitzan conjectured the multiplicative connection inequality
\cite[Conjecture~1]{KozmaNitzan2024} and showed that their weaker
uniform near-one gluing Conjecture~3 implies critical nonpercolation
on $\Z^d$ for every $d\ge2$ \cite[Theorem~6]{KozmaNitzan2024}.
Leder's public account reports a Lean formalization of that lattice
conclusion and displays the first-contact comparison (GEN)
\cite[Section~3.4]{Leder2026}. Although the account does not claim
Conjecture~1, (GEN) implies the finite joint inequality: take its
increasing cluster functional to be the indicator of meeting the
target and bound the resulting weighted mean by its minimum.
The subsequent public manuscript \cite{ConnectionInequalities2026}
explicitly records this consequence and stronger finite connection
comparisons. Its public site-percolation extension
\cite{SiteCriticality2026} treats independent labelled hyperedges
and critical site percolation on $\Z^d$ for $d\ge3$. We give a direct
joint-gluing proof with this antecedent credit. These finite and
lattice results do not assert Theorem~\ref{thm:main} for general
quasi-transitive graphs.
The probabilistic tools are developed with their local predecessors
at their points of use. The adjacent-cluster bound adapts the
boundary-discrepancy method of Aizenman, Kesten, and Newman
\cite[Section~3]{AizenmanKestenNewman1987} and Hutchcroft's
ghost-field formulation \cite[Section~3]{Hutchcroft2020Locality}.
Conditional association was developed by van den Berg and Kahn
\cite{VanDenBergKahn2001}; alternating conditional-cluster resampling
is the method of van den Berg, H\"aggstr\"om, and Kahn
\cite{VanDenBergHaggstromKahn2006}. Decision-tree inequalities
\cite{OSSS2005,DuminilCopinRaoufiTassion2019} provide related links
between exploration and pivotality; here the local estimate uses
the martingale of conditional connection probabilities. The entropy
bound accommodates adaptive read sets whose overlap is controlled
only under a comparison law, beyond the fixed-set setting of
Shearer's inequality and its relative-entropy forms
\cite{ChungGrahamFranklShearer1986,MadimanTetali2010}.
The geometric construction adapts the seed and adaptive-block
strategy of Grimmett and Marstrand \cite{GrimmettMarstrand1990}
and the fresh-collar and stored-prediction arguments of Kozma and
Nitzan \cite[Lemma~10 and proof of Theorem~6]{KozmaNitzan2024}.
Critical extinction in each fixed slab
\cite{DuminilCopinSidoraviciusTassion2016Slabs} does not alone give
the full-lattice conclusion. Choosing useful directions by exit
probabilities is related to Martineau and Tassion's parallelogram
construction \cite{MartineauTassion2017}. Here the two-direction
argument and the conditional-failure boundary count are carried out
on the original graph, including when the reveal domains are countable.
The structural reduction runs from Gromov's polynomial-growth
theorem \cite{Gromov1981} through Trofimov's graph and
near-polynomial-growth theorems \cite{Trofimov1985,Trofimov2003}
to Tessera and Tointon's one-scale theorem
\cite[Corollary~2.4]{TesseraTointon2021}. The latter develops the
approximate-group method of Breuillard, Green, and Tao
\cite{BreuillardGreenTao2012} and supplies the quotient action and
stabilizer information used here. Related nilpotent quotients occur
in percolation locality on polynomial-growth graphs
\cite{ContrerasMartineauTassion2023Locality}. In this paper the
quotient supplies coordinates; every connection and exposure uses
original edges.
==== END No-percolation-at-criticality-on-quasi-transitive-graphs//introduction.tex ====
==== BEGIN No-percolation-at-criticality-on-quasi-transitive-graphs//main.tex ====
\documentclass[11pt]{article}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{lmodern}
\usepackage{microtype}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage{enumitem,booktabs,graphicx,xcolor}
\usepackage{flafter,xurl}
\usepackage{tikz}
\usetikzlibrary{arrows.meta,calc,patterns,shapes.geometric}
\usepackage[numbers,sort&compress]{natbib}
\usepackage[colorlinks=true,linkcolor=blue!45!black,citecolor=blue!45!black,
urlcolor=blue!45!black,pdftitle={No percolation at criticality on quasi-transitive graphs},
pdfauthor={OpenAI}]{hyperref}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}
\newcommand{\PP}{\mathbb P}
\newcommand{\EE}{\mathbb E}
\newcommand{\pc}{p_c}
\newcommand{\R}{\mathbb R}
\newcommand{\Z}{\mathbb Z}
\newcommand{\N}{\mathbb N}
\DeclareMathOperator{\Var}{Var}
\DeclareMathOperator{\Cov}{Cov}
\DeclareMathOperator{\Ent}{Ent}
\DeclareMathOperator{\Aut}{Aut}
\DeclareMathOperator{\osc}{osc}
\DeclareMathOperator{\dist}{dist}
\setlength{\emergencystretch}{1.5em}
\setcounter{tocdepth}{2}
\title{No percolation at criticality on quasi-transitive graphs}
\author{OpenAI}
\date{September 24, 2026}
\begin{document}
\maketitle
\begin{abstract}
We prove that critical Bernoulli bond percolation has no infinite
cluster on any infinite connected locally finite quasi-transitive graph
with critical probability less than one. This resolves the bond form of
the criticality conjecture of Benjamini and Schramm.
\end{abstract}
\tableofcontents
\input{sections/introduction}
\input{sections/preliminaries}
\input{sections/two-cluster-dfs-entropy}
\input{sections/interpolation}
\input{sections/superpolynomial}
\input{sections/gluing}
\input{sections/structure}
\input{sections/moves}
\input{sections/corridor-exploration}
\input{sections/assembly}
\bibliographystyle{plainnat}
\bibliography{references}
\end{document}
==== END No-percolation-at-criticality-on-quasi-transitive-graphs//main.tex ====
==== BEGIN No-percolation-at-criticality-on-quasi-transitive-graphs//moves.tex ====
\begin{figure}[htbp]
\centering
\begin{tikzpicture}[x=1cm,y=1cm,>=Stealth]
\begin{scope}[shift={(-3.1,0)}]
\draw[fill=blue!3,draw=blue!50!black] (0,0) circle (1.65);
\foreach \ang in {0,45,...,315}{
\draw[black!18] (0,0)--(\ang:1.65);
\fill[blue!65!black] (\ang:1.65) circle(.035);
\begin{scope}[shift={(\ang:1.65)},rotate={\ang/2+90}]
\draw[blue!70!black,line width=1.1pt] (-.19,0)--(.19,0);
\end{scope}
}
\node[fill=white,inner sep=3pt,align=center] at (0,0)
{$s=0$\\$A=WI$};
\draw[->,black!60] (15:2) arc[start angle=15,end angle=65,radius=2];
\node[above] at (0,2.08) {$s=1$};
\node[below=6pt,align=center,text width=4.9cm] at (0,-1.8)
{Boundary center lines follow the minor axes.};
\end{scope}
\begin{scope}[shift={(2.65,-.05)}]
\draw[->,black!45] (-.25,0)--(2.35,0) node[right] {$t$};
\draw[->,black!45] (0,-1.65)--(0,1.7) node[above] {$z$};
\draw[->,blue!65!black,line width=1pt] (0,0)--(1.65,1.3);
\draw[->,blue!65!black,line width=1pt] (0,0)--(1.65,-1.3);
\draw[fill=blue!8,draw=blue!55!black] (1.5,1.15) rectangle (1.8,1.45);
\draw[fill=blue!8,draw=blue!55!black] (1.5,-1.45) rectangle (1.8,-1.15);
\fill (0,0) circle(.035);
\node[right=5pt] at (1.8,1.3) {$(1,1)$};
\node[right=5pt] at (1.8,-1.3) {$(1,-1)$};
\node[below=6pt,align=center,text width=4.6cm] at (1,-1.75)
{A linear map normalizes two separated directions.};
\end{scope}
\end{tikzpicture}
\caption{The direction argument in Proposition~\ref{prop:moves}.
Left: the ellipse parameters form a disk; on its boundary, favored
unoriented lines have doubled angles with winding number one.
They therefore cannot vary by a small angle across every edge of
a triangulation. Right: two separated favored directions yield
the required moves. The endpoint error boxes are enlarged for clarity.}
\label{fig:moves}
\end{figure}
==== END No-percolation-at-criticality-on-quasi-transitive-graphs//moves.tex ====
==== BEGIN No-percolation-at-criticality-on-quasi-transitive-graphs//preliminaries.tex ====
\section{Uniformity and the growth alternatives}
\label{sec:preliminaries}
We record the reductions needed to use finite arguments uniformly on
the infinite graph. Graph distance always counts edges. Unless
specified otherwise, balls are induced subgraphs as well as vertex
sets. The maximum degree is denoted by $D$.
\subsection{Graph conventions and the threshold}
It suffices to prove Theorem~\ref{thm:main} for simple graphs.
Indeed, loops have no effect on clusters. If parallel edges occur,
subdivide each edge once, using a distinct new vertex for each edge.
The resulting graph is simple and remains connected and locally
finite. There are finitely many edge orbits, since there are finitely
many vertex orbits and each representative has finite degree.
Lifting the original automorphisms therefore proves quasi-transitivity
of the subdivided graph. At parameter $t$, each original edge is
fully traversable with probability $t^2$, independently of the others.
An infinite cluster in the subdivided graph contains infinitely many
original vertices, by local finiteness. Thus percolation on it occurs
exactly when the effective configuration on the original graph
percolates, and its critical probability is $\sqrt{\pc(G)}$.
The simple-graph conclusion at this parameter gives the desired
conclusion on $G$.
Henceforth the infinite graph is simple. Finite auxiliary graphs may
have parallel edges after contractions. Local finiteness and
connectedness imply countability. Finitely many vertex orbits imply $D<\infty$.
For $p<1/D$, the probability of an open simple path of length $n$
starting at $x$ is at most $D^np^n$, which tends to zero. An infinite
cluster would contain such a path for every $n$, so
\begin{equation}
\label{eq:positive-threshold}
\pc\ge 1/D>0.
\end{equation}
The event that some infinite cluster exists is unchanged by altering
finitely many edge states: adding finitely many edges joins only
finitely many clusters, and deleting finitely many edges splits an
infinite cluster into finitely many pieces. It is therefore a tail
event and has probability zero or one. Monotonicity in $p$ shows that
our definition of $\pc$ agrees with the supremum of the parameters
at which almost surely every cluster is finite. In particular all
clusters are finite almost surely for $p<\pc$.
We use Harris's inequality: increasing functions of independent
edge states have nonnegative covariance \cite{Harris1960}.
For finitely many bits, this follows by induction from the covariance
decomposition after conditioning on one bit; the two conditional
means are themselves increasing. For bounded functions of countably
many bits, conditional expectations on finite sets of coordinates
and martingale convergence give the same conclusion. Decreasing
functions are likewise positively correlated; an increasing and a
decreasing function are negatively correlated.
If critical percolation occurs with positive probability, countability
gives a vertex $x$ with $\PP_{\pc}(|C_x|=\infty)>0$.
For a fixed path from $y$ to $x$, Harris's inequality bounds
$\PP_{\pc}(|C_y|=\infty)$ below by this positive probability times
$\pc$ to the path length. Finitely many vertex orbits then give
\begin{equation}
\label{eq:uniform-jump}
\theta:=\min_{x\in V}\PP_{\pc}(|C_x|=\infty)>0.
\end{equation}
This uniform lower bound is the contradiction hypothesis in both
subexponential arguments.
\subsection{Ball comparisons}
\begin{lemma}
\label{lem:orbit-growth}
There is an integer $C_0$ such that every vertex orbit meets every
ball of radius $C_0$. Moreover, for nonnegative integer radii,
\begin{equation}
\label{eq:ball-comparisons}
V_+(r)\le V_-(r+C_0),\qquad
V_+(r+s)\le V_+(r)V_+(s).
\end{equation}
The limit $\gamma=\lim_{r\to\infty}V_+(r)^{1/r}$ exists. If
$\gamma>1$, every vertex ball has exponential growth; if $\gamma=1$,
then $\log V_+(r)=o(r)$.
\end{lemma}
\begin{proof}
Choose a representative in each of the finitely many orbits. For
each representative and each orbit, fix a path to that orbit, and
let $C_0$ bound the lengths of these finitely many paths. Translating
them proves the density assertion. To compare balls, move the center
of a ball attaining $V_+(r)$ within distance $C_0$ of a center attaining
$V_-(r+C_0)$. The translated smaller ball lies in the larger one.
Also $B(x,r+s)$ is covered by the radius-$s$ balls centered in
$B(x,r)$, proving the second inequality.
Thus $\log V_+(r)$ is subadditive. Dividing a radius into blocks of
any fixed length shows that its quotient by $r$ converges to its
infimum. This proves existence of $\gamma$. Finally
$V_+(r-C_0)\le |B(x,r)|\le V_+(r)$ for $r\ge C_0$ gives the claimed
uniform growth conclusions.
\end{proof}
We now invoke precisely the following external result.
\begin{theorem}[Hutchcroft {\cite[Theorem~1.2]{Hutchcroft2016}}]
\label{thm:exponential}
If a connected locally finite quasi-transitive graph satisfies
$\liminf_{r\to\infty}|B(x,r)|^{1/r}>1$, then it has almost surely no
infinite Bernoulli bond cluster at its critical probability.
\end{theorem}
It remains to work under $\log V_+(r)=o(r)$. Either
\begin{equation}
\label{eq:superpoly-growth}
\frac{\log V_-(r)}{\log r}\longrightarrow\infty,
\end{equation}
or this quotient is bounded along an unbounded sequence of integer
radii. In the latter case there is a finite $d$ such that
\begin{equation}
\label{eq:polynomial-subsequence}
V_-(r)\le r^d
\quad\text{along that sequence.}
\end{equation}
These alternatives are exhaustive, including when the quotient
oscillates.
\subsection{Exact clusters and finite witnesses}
Conditioning on the exact vertex set of a cluster fixes its boundary
edges closed and imposes only an internal connectivity condition.
Consequently the edges induced outside that set keep their product
law. Revealing every incident edge, including internal edges,
has the same property. We will specify which of these two exposures
is being used.
The event $|C_x|\ge s$, for a fixed positive integer $s$, can be
witnessed inside $B(x,s-1)$: a connected cluster of at least $s$
vertices contains a connected set of $s$ vertices containing $x$.
Its probability is therefore continuous in $p$. A connection between
fixed finite sets is the increasing union of connections in finite
induced subgraphs. Its probability can be approximated from below
by such finite events, at the same parameter $p$. These observations
also apply uniformly to finitely many vertex or pair orbits.
==== END No-percolation-at-criticality-on-quasi-transitive-graphs//preliminaries.tex ====
==== BEGIN No-percolation-at-criticality-on-quasi-transitive-graphs//sections/interpolation.tex ====
\section{Finite interpolation}\label{sec:interpolation}
The depth-first and entropy estimates let us move two large distinct
clusters from the ends of a path to the ends of one edge. Binary
subdivision limits the number of new clusters used to a logarithm of
the path length. We must also control the probability cost of joining
these clusters; counting the opened edges alone does not control how
many original configurations can produce the same output.
\begin{proposition}[Interpolation along a path]\label{prop:interpolation}
Let $\mu$ be Bernoulli bond percolation with parameter $p\in(0,1)$ on
a finite undirected graph, and put $q=1-p$. Let
$x_0,x_1,\ldots,x_d$ be a simple path, with $d\ge2$. Suppose that
\[
\mu(x_j\leftrightarrow x_k)\ge c>0
\qquad(0\le j<k\le d,\ k-j<d).
\]
For an integer $s\ge1$, suppose that the clusters of $x_0,x_d$ are
distinct and both have at least $s$ vertices with probability
$\delta>0$. There is a path edge $e$ such that
\[
-\log\mu(H_s(e))
\le C\bigl(\log(1/\delta)+\lceil\log_2d\rceil+1\bigr).
\]
Here $H_s(e)$ is the event that the endpoint clusters of $e$ are
distinct and each has at least $s$ vertices. The constant $C$ depends
only on $c$ and positive lower bounds for $p$ and $q$.
\end{proposition}
Recall that for probability laws $P,R$ on a finite space,
\[
D(P\Vert R)=\sum_x P(x)\log\frac{P(x)}{R(x)}
\]
is their relative entropy, with zero summands omitted. We will construct
a law $Q_\eta$ supported on $H_s(e)$ for a fixed path edge $e$, with
relative entropy of order $\log(1/\delta)+\log d$ from $\mu$.
Since any law supported on an event of probability $u$ has relative
entropy at least $\log(1/u)$, this will prove the proposition.
We construct $Q_\eta$ by opening contacts along two chains of clusters.
A reverse procedure that guesses and closes these contacts will account
for the possible multiplicity of the opening map.
An exact incidence exposure of a cluster records its vertex set and the
states of every edge with at least one endpoint in that set, including
internal edges skipped by a lazy search. All edges wholly outside the
exposed set retain their product law. We will repeatedly use this
observation for unions of distinct clusters.
\subsection{Contact weights and normalized exposures}
We first record the normalization that makes the construction possible.
Suppose a union $O$ of exact clusters has been exposed, a deterministic
target set $\mathcal A$ is contained in $O$, and $w\notin O$.
Run the deterministic lazy depth-first search of Lemma~\ref{lem:dfs}
from $w$ towards $\mathcal A$. For every query $f$, let $h$ be the
conditional probability of $w\leftrightarrow\mathcal A$ under the
\emph{original product law $\mu$, conditioned only on this search's
own query prefix}. Write $h_0,h_1$ for the two continuations and
$d_f=h_1-h_0\ge0$. Thus $h=ph_1+qh_0$.
A contact is a queried edge from the newly explored cluster into $O$.
Every contact is closed in the exposed configuration. Give it weight
\[
a_f=pd_f,
\qquad A=\sum_{\text{queried contacts }f}a_f,
\qquad h_* =\mu(w\leftrightarrow\mathcal A).
\]
The numbers $d_f$ are not recomputed under the law conditioned on $O$.
This distinction is essential: under that conditioned law a contact is
forced closed, and the ordinary conditional probability drops by
$h-h_0=pd_f$. Every noncontact query is a fresh Bernoulli bit, so its
conditional expected change in $h$ is zero. The search fails and its
final prefix certifies failure even under $\mu$, since it has queried
all edges leaving the cluster of $w$. Telescoping therefore gives
\begin{equation}\label{eq:contact-normalization}
\EE_{\mathrm{ext}}A=h_*.
\end{equation}
Here the expectation samples only the product exterior of the fixed
incidence exposure.
Conditional on the fixed incidence exposure and any query prefix, the
same telescoping gives expected remaining contact weight at most one.
The potential $h$ still uses only the search's own prefix. Since each
contact weight is at most one,
expansion of the square yields
\begin{equation}\label{eq:contact-second-moment}
\EE_{\mathrm{ext}}A^2
\le \EE_{\mathrm{ext}}\sum_f a_f
+2\EE_{\mathrm{ext}}\sum_f a_f
\le3.
\end{equation}
In the middle expression the second sum bounds each contact weight
multiplied by the conditional expected sum of subsequent weights.
Consequently, when $h_*>0$, the rule
\begin{equation}\label{eq:marked-contact-law}
\frac{a_f}{h_*}\,\mu_{\mathrm{ext}}(d\omega)
\quad\text{on exterior configurations and a chosen contact }f
\end{equation}
defines a probability measure, with counting measure on the contact
coordinate.
After this choice, expose the exact incidence configuration of the
new cluster $K=C_w$. The chosen contact, its query prefix, and its
weight are determined by the old exposure and the incidence states of
$K$. Thus the factor in \eqref{eq:marked-contact-law} imposes no
condition on edges wholly outside $O\cup K$. Conditional on the new
exposure and chosen contact, those edges still have product law.
This proves both normalization and preservation of the exterior law
at each successive exposure.
\subsection{Binary interpolation and its description}
Let $J=\lceil\log_2d\rceil$. Start with the product law conditioned
on the endpoint event in Proposition~\ref{prop:interpolation}. Expose
the two endpoint clusters, calling them the left and right bases, and
assign every vertex in each base its respective side.
Maintain an interval of the path whose endpoints have opposite sides.
At a step $i$, take its midpoint $w_i$, using the lower index in a tie,
and set
\[
\mathcal A_i=\{x_0,x_d,w_1,\ldots,w_{i-1}\}.
\]
Every target anchor belongs to a previously exposed cluster. If $w_i$
already lies in their union $O$, make no new exposure and give it its
cluster's side; call this a hold. Otherwise apply
\eqref{eq:marked-contact-law} with $w=w_i$ and
$\mathcal A=\mathcal A_i$, expose $K_i=C_{w_i}$, and record its
chosen contact $f_i$. The cluster containing the head of $f_i$ is its
parent, and $K_i$ inherits that parent's side. Leave $f_i$ closed.
Retain the subinterval joining $w_i$ to the endpoint of opposite side.
The new interval has length at most the ceiling of half the old length,
so after $\ell\le J$ steps its endpoints are adjacent. At each
nonhold step, one current endpoint is a target anchor at path-index
distance strictly less than $d$ from $w_i$. Therefore
\begin{equation}\label{eq:interpolation-root-bound}
h_i:=\mu(w_i\leftrightarrow\mathcal A_i)\ge c.
\end{equation}
The preceding normalization constructs a joint law of a common final
configuration $\Omega$ and its chosen contacts. Equivalently, one
successively multiplies the conditional exterior law by the normalized
factors \eqref{eq:marked-contact-law}; each factor is measurable in the
new frozen incidence data, so later exterior sampling preserves all
earlier factors.
The parent relations form a forest rooted at the two bases. Call a
nonbase cluster active if it lies on the ancestry path from the owner
of one terminal endpoint to its base. The active clusters on each side
form one chain. Record a descriptor consisting of the number of steps,
the side and hold bit at each step, and the active indices. There are
at most $\sum_{j=0}^J8^j\le8^{J+1}$ descriptors. Condition on one of
maximum probability and denote the resulting joint law by $Q$.
All midpoints, target sets, nonhold indices $I$, active indices $I_*$,
and the terminal edge are now deterministic. Moreover, the parent of
an active index is the preceding active index on its side, or its base
if there is none. Indeed, the active indices on that side are exactly
one ancestry chain, ordered by creation time. Thus every active parent
has a deterministic anchor.
\input{figures/interpolation}
Relative to $\mu$ on configurations and counting measure on the
contacts indexed by $I$, the joint density satisfies
\begin{equation}\label{eq:interpolation-density}
\frac{dQ}{d(\mu\otimes\mathrm{count})}
\le e^L\prod_{i\in I}a_i,
\qquad a_i=pd_{f_i},
\qquad
L=\log(1/\delta)+(J+1)\log8+J\log(1/c).
\end{equation}
The three costs are the endpoint conditioning, descriptor conditioning,
and the normalizers \eqref{eq:interpolation-root-bound}.
\subsection{The two chains and their inverse}
Open only the active contacts in $\Omega$, and call the resulting
configuration $\eta$. Each terminal endpoint is now joined along its
active ancestry chain to a base cluster of size at least $s$. The two
resulting clusters remain distinct: all original cluster boundaries were
closed, and the only newly opened edges join clusters within one of the
two same-side chains. Thus $Q_\eta$ is supported on $H_s(e)$ for the
terminal edge fixed by the descriptor.
We next give a reverse procedure and compute its probability of recovering
the chosen contacts. This computation will identify the quantities that
the remaining entropy estimates must control.
For the fixed schedule, expose all anchor clusters in order on an
ordinary product configuration. Let $A_i$ be the sum of the contact
weights at step $i$, with $A_i=1$ when $w_i$ is already exposed. These
quantities depend only on the configuration and schedule, not on earlier
contact choices: the exposed union is exactly the union of the clusters
of the preceding anchors. Write
\[
X=\sum_{i\in I}\log^+A_i,
\qquad \log^+t=\log\max\{1,t\}.
\]
For each active $i$, let $t_i$ be a standalone deterministic transcript
that exposes the two exact clusters at $w_i$ and its parent anchor,
querying all their incidence edges and caching duplicate queries.
For an ordinary pair transcript $t$, call a contact $f$ admissible if
the cluster at $w_i$ avoids $\mathcal A_i$ and its depth-first search
queries $f$ closed into the distinct parent cluster. Every pair selected
under $Q$ is admissible.
Open just $f$ in an admissible configuration. It becomes the sole open
exit from the original cluster of $w_i$, and the parent contains a target
anchor. Hence $f$ is a queried actual open pivot. Let $S_i(t,f)$ be the
sum of the weights $qd$ of queried actual open pivots through $f$ in this
modified search, including $f$ itself. This number is determined by
$(t,f)$. The prefix through $f$ uses only incidences of the original
cluster at $w_i$; an earlier queried open edge is an actual pivot exactly
when deleting it separates $w_i$ from the tail of $f$ within that cluster.
The exact incidence transcript records all the internal edges needed for
this test.
Construct a reference probability $R$ on output configurations and marks
as follows. First sample $\eta$ under $\mu$. On a working copy, process
the active indices in descending order. At index $i$, run the
$\mathcal A_i$ depth-first search from $w_i$. For each queried actual open
pivot of weight $b_f=qd_f$, let $S_f$ be the cumulative weight through it,
and give that pivot guess probability
\begin{equation}\label{eq:interpolation-inverse-guess}
\pi_i(f)=\frac{b_f}{(1+S_f)^2}.
\end{equation}
The sum of these probabilities is at most
$\int_0^\infty(1+t)^{-2}\,dt=1$, by comparison with the integral on
each cumulative-weight interval. Assign the remaining probability to
a dummy guess. Close the guessed pivot and continue, using arbitrary
dummy defaults after an invalid history. After all active guesses, on
the recovered working copy guess each inactive contact independently
with probabilities $a_f/A_i$, again using a dummy default if necessary.
The configuration marginal of $R$ is $\mu$.
We verify that the true inverse guesses have precisely the weights just
defined. At active step $i$, all later active contacts have already been
closed. Every earlier active contact has both endpoints in original
clusters created before $K_i$, since a contact joins its new cluster to
an older parent. Thus none of those earlier contacts touches $K_i$.
Its only open boundary edge in the current working copy is $f_i$, and
its parent still contains the deterministic target anchor. The search
prefix through $f_i$, its original-product conditional differences
$d_f$, and the criterion for earlier actual pivots are therefore unchanged
from the configuration with only $f_i$ opened. In particular, the guess
$f_i$ is available with cumulative weight exactly $S_i$. Holds add target
anchors but no new cluster or switched edge, so they do not affect this
argument.
The active contacts are distinct: different nonhold indices create
distinct original clusters, and each contact joins its new cluster to
an older one. Consequently the map
$(\Omega,(f_i))\mapsto(\eta,(f_i))$ is injective. Along the true inverse
history, \eqref{eq:interpolation-density} bounds the ratio of the joint
output density to $R$ by
\[
e^L\prod_{i\in I_*}
\frac{(q/p)a_i}{qd_{f_i}/(1+S_i)^2}
\prod_{i\in I\setminus I_*}A_i
=e^L\prod_{i\in I_*}(1+S_i)^2
\prod_{i\in I\setminus I_*}A_i.
\]
Here $q/p$ is the original-to-opened Bernoulli likelihood ratio for each
active contact. It cancels because the forward weight is $a_i=pd_{f_i}$
and the inverse guess has numerator $qd_{f_i}$.
Taking logarithms and discarding the marks by data processing gives
\begin{equation}\label{eq:interpolation-cost-to-bound}
D(Q_\eta\Vert\mu)
\le L+2\EE_Q\sum_{i\in I_*}\log(1+S_i)+\EE_Q X.
\end{equation}
It remains to bound the two expectations on the right by a constant
times $L+J$. We do this under the closed-contact law $Q$, before opening
any edge.
\subsection{Entropy of the sampled configuration}
We use the same formula for $D(P\Vert R)$ when $R$ is a nonnegative finite
measure rather than a probability; in that case it need not be
nonnegative. For $P\ll R$, Jensen's inequality gives
\begin{equation}\label{eq:interpolation-entropy-inequality}
\EE_P g\le D(P\Vert R)+\log\sum R e^g.
\end{equation}
Write $Q_\Omega$ for the configuration marginal of $Q$ and put
$D_\Omega=D(Q_\Omega\Vert\mu)$.
By \eqref{eq:contact-second-moment},
\[
\EE_\mu[\max(1,A_i)^2\mid\text{previous exact exposures}]\le4.
\]
Each $A_i$ is known after the next exact exposure. Successive conditional
expectation therefore gives
$\EE_\mu e^{2X}\le4^J$. Summing the density bound
\eqref{eq:interpolation-density} over the possible contact choices,
which only enlarges the sum if the descriptor restrictions are dropped,
gives
\[
D_\Omega\le L+\EE_Q X.
\]
Applying \eqref{eq:interpolation-entropy-inequality} to $2X$ gives
$2\EE_Q X\le D_\Omega+J\log4$. Hence
\begin{equation}\label{eq:interpolation-configuration-entropy}
D_\Omega\le2L+J\log4,
\qquad \EE_Q X\le L+J\log4.
\end{equation}
\subsection{Entropy of the inverse guesses}
We now estimate the sum involving $S_i$. The pair transcripts $t_i$
contain just the cluster data needed to determine each marked weight.
On the support of $Q$, every cluster occurs in at most two such pairs,
and an edge is incident to at most two clusters. Each bit is therefore
read by at most four pair algorithms. Lemma~\ref{lem:entropy} gives
\begin{equation}\label{eq:interpolation-pair-entropy}
\sum_{i\in I_*}D(Q_{t_i}\Vert\mu_{t_i})\le C_pD_\Omega,
\end{equation}
with $C_p$ uniform when $p,q$ are bounded below. The multiplicity
condition is needed only on the support of $Q$.
For each active $i$, define a finite measure on marked pair transcripts by
\[
\nu_i(t,f)=\mu_{t_i}(t)\,pd_f
\quad\text{for admissible }(t,f),
\]
and zero otherwise. This reference measure combines the original pair
transcript law with the contact weight used in the forward sampling.
It need not have mass one. Its usefulness is the following bound, which
converts the cost of an inverse guess to the pivotal second moment.
The map that opens $f$ and records $f$ is injective on full marked
configurations. The original-to-modified product probability ratio is
$q/p$, so multiplying the original weight $pd_f$ gives the modified
weight $qd_f$. In any modified configuration, the admissible inverse
marks are a subset of its queried actual open pivots. Their cumulative
weights are at most the total $W$ from Lemma~\ref{lem:dfs}. Therefore
\begin{equation}\label{eq:interpolation-contact-measure}
\sum_{t,f}\nu_i(t,f)(1+S_i(t,f))
\le\EE_\mu[W(1+W)]\le4.
\end{equation}
We next control the entropy of the chosen marks, not just that of their
pair transcripts. Write $\mathcal H(\cdot\mid\cdot)$ for conditional
Shannon entropy. Taking logarithms in
\eqref{eq:interpolation-density} and averaging yields
\begin{equation}\label{eq:interpolation-joint-contact-cost}
D_\Omega+\sum_{i\in I}\EE_Q\log(1/a_i)
-\mathcal H((f_i)_{i\in I}\mid\Omega)\le L.
\end{equation}
Since $t_i$ is determined by $\Omega$,
\[
\mathcal H((f_i)_{i\in I}\mid\Omega)
\le\sum_{i\in I_*}\mathcal H(f_i\mid t_i)
+\sum_{i\in I\setminus I_*}\mathcal H(f_i\mid\Omega).
\]
For an inactive index, nonnegativity of conditional relative entropy
to the probabilities $a_f/A_i$ gives
\[
\EE_Q\log(1/a_i)-\mathcal H(f_i\mid\Omega)
\ge-\EE_Q\log A_i.
\]
Combining these inequalities with
\eqref{eq:interpolation-configuration-entropy} and
\eqref{eq:interpolation-pair-entropy}, we obtain
\begin{align*}
\sum_{i\in I_*}D(Q_{t_i,f_i}\Vert\nu_i)
&=\sum_{i\in I_*}\left[
D(Q_{t_i}\Vert\mu_{t_i})+
\EE_Q\log(1/a_i)-\mathcal H(f_i\mid t_i)\right]\\
&\le C_pD_\Omega+L+\EE_Q X
\le C'_p(L+J).
\end{align*}
All chosen weights are positive, and all spaces are finite, so these
expressions are finite on the support of $Q$.
Apply \eqref{eq:interpolation-entropy-inequality} with
$g=\log(1+S_i)$ and use
\eqref{eq:interpolation-contact-measure}. This proves
\begin{equation}\label{eq:interpolation-inverse-cost}
\EE_Q\sum_{i\in I_*}\log(1+S_i)\le C''_p(L+J).
\end{equation}
Substituting \eqref{eq:interpolation-configuration-entropy} and
\eqref{eq:interpolation-inverse-cost} into
\eqref{eq:interpolation-cost-to-bound} yields
\begin{equation}\label{eq:interpolation-output-entropy}
D(Q_\eta\Vert\mu)\le C'''_p(L+J).
\end{equation}
We already proved that $Q_\eta$ is supported on $H_s(e)$. If
$u=\mu(H_s(e))$, conditioning $\mu$ on this event gives
$D(Q_\eta\Vert\mu)\ge\log(1/u)$.
Together with the definition of $L$, the last display proves
Proposition~\ref{prop:interpolation}.
==== END No-percolation-at-criticality-on-quasi-transitive-graphs//sections/interpolation.tex ====
==== BEGIN No-percolation-at-criticality-on-quasi-transitive-graphs//sections/moves.tex ====
\section{Two approximate coordinate moves}\label{sec:moves}
The quotient coordinates have bounded edge increments, but no symmetry
need interchange their directions. We obtain two directions from
connection probabilities, then normalize them by a linear map. The
interface needed for the corridors is that the seed radius is fixed
before the coordinate increments are made small.
\begin{proposition}[Approximate moves]\label{prop:moves}
Let $G$ be an infinite connected locally finite graph and let a group
$\Lambda$ act on it by automorphisms with finitely many vertex orbits.
Let $\pi:V(G)\to\mathbb Z^2$ be onto, with edge increments
bounded in Euclidean norm by $D_\pi$ and with
$\pi(gx)=\pi(x)+a_g$, where
$g\mapsto a_g$ is an epimorphism from $\Lambda$ to $\mathbb Z^2$.
Suppose $0<\pc<1$ and, at $\pc$, there is almost surely a unique
infinite cluster and no infinite open ray with bounded $\pi$-projection.
For every \(0<e,\eta<1/10\), there is an integer \(m\) such that
for every requested \(\rho_0>0\) one can choose an invertible linear map
\(\Phi:\mathbb R^2\to\mathbb R^2\) and a parameter
\(p'\in[\pc/2,\pc)\) with the following properties.
The coordinates \((t,z)=\Phi\pi\) have edge increments at most
\(\rho_0\) in supremum norm. For $y\in V(G)$ and
$s\in\{-1,1\}$, let $E_s(y)$ be the event that an open path starts
in $B(y,m)$, stays within supremum coordinate distance $100$ of $y$,
and ends within supremum distance $e/4$ of
$(t(y)+1,z(y)+s)$. Then
\[
\PP_{p'}(E_s(y))\ge1-\eta
\qquad(y\in V(G),\ s\in\{-1,1\}).
\]
The radius $m$ is chosen before $\rho_0$.
\end{proposition}
We verify the uniqueness hypothesis for the subexponential graph in
our induction before proving the proposition. The adjacent-cluster
bound supplies this fact without any coordinate assumptions.
\begin{lemma}[Uniqueness under subexponential growth]\label{lem:uniqueness}
Let $G$ be infinite, connected, locally finite and quasi-transitive, with
$\log V_+(r)=o(r)$. If $p\in(0,1)$ and Bernoulli bond percolation at $p$
has an infinite cluster with positive probability, then it has exactly
one infinite cluster almost surely.
\end{lemma}
\begin{proof}
Letting $s\to\infty$ in Proposition~\ref{prop:two-cluster} shows that,
for every edge, the probability that its endpoints lie in distinct
infinite clusters is zero. We show that this excludes any two infinite
clusters, even if no edge initially joins them.
Otherwise countability gives fixed vertices $x,y$ that belong to
distinct infinite clusters with positive probability. Choose a fixed
simple path $x=x_0,x_1,\ldots,x_d=y$. On that event let $j$ be the
first index with $x_j\in C_y$; some fixed $j\ge1$ occurs on a
positive-probability subevent. Force the finitely many prefix edges
$x_ix_{i+1}$ for $0\le i<j-1$ open (none if $j=1$). Every endpoint of these edges
was outside $C_y$, so this modification leaves $C_y$ unchanged.
It makes $C_{x_{j-1}}$ infinite through $x$, while that cluster
remains distinct from $C_{x_j}=C_y$. The modified event still has
positive probability: condition on all unmodified bits and use that
the all-open state of the finite prefix has positive conditional
probability. This contradicts the preceding conclusion for the
fixed edge $x_{j-1}x_j$. Thus there is at most one infinite cluster
almost surely. Existence is a tail event, so its assumed positive
probability is one.
\end{proof}
Under the contradiction hypothesis used to prove
Theorem~\ref{thm:structured}, this lemma
and Lemma~\ref{lem:bounded-projection} verify the two percolation
hypotheses of Proposition~\ref{prop:moves}. The equivariant onto
coordinates and their bounded increments were established in
Section~\ref{sec:structure}. The proposition's proof uses only its
stated hypotheses; in particular, absence of bounded-projection rays
is an input supplied by the induction, not by the coordinate map alone.
Choosing geometry by exit probabilities also appears in Martineau and
Tassion's parallelogram construction
\cite[Section~3.2]{MartineauTassion2017}. The proof here obtains the two
directions either from a disk of ellipses or from a projected strip.
\begin{proof}[Proof of Proposition~\ref{prop:moves}]
Choose $o$ with $\pi(o)=0$ and put $\zeta=e/1000$.
Countability gives a vertex with positive infinite-cluster probability.
Harris's inequality transfers this positivity along fixed paths to each
of the finitely many orbit representatives. Hence
\[
\theta:=\min_x\PP_{\pc}(|C_x|=\infty)>0.
\]
For each fixed nonzero linear functional \(\ell\) on \(\mathbb R^2\),
the unique infinite cluster is unbounded above in \(\ell\circ\pi\),
almost surely. Indeed, the union of all infinite clusters meets
\(\{\ell\circ\pi>r\}\) with probability at least \(\theta\), by
choosing one vertex there. Its unboundedness above is a tail event:
changing finitely many edges changes that union by at most finitely
many vertices. Continuity from above and the zero-one law give
probability one, and uniqueness gives the stated conclusion.
We first construct the two events at \(o\) and at \(\pc\), with error
smaller than \(e/8\) and failure probability smaller than \(\eta/10\).
In each of the two cases below the seed is chosen before the scales
that make the coordinate map small. Only after fixing the map will we
lower the percolation parameter.
\emph{Case 1: no fixed direction supports a strip ray with positive
probability.} For a unit vector $d$, a centered strip means
$\{x:|d^\perp\cdot\pi(x)|\le w\}$ for some finite $w$. Translated
strips are contained in wider centered strips. In this case the
probability of a ray in such a strip is zero for each fixed $d$.
We do not need a statement about the union over all directions.
Cover the unit circle by $M$ arcs of angular radius at most $\zeta$,
with signed unit centers. Choose $m_0$ so that $B(o,m_0)$ hits the
infinite cluster with probability greater than $1-(\eta/20)^M$.
This choice does not involve any later scale. Fix an arbitrarily large
$W$ containing the seed projections well inside the Euclidean ball of
radius $W$. For $U\ge W$, consider the positive matrices
\[
A(s,\varphi)=R_\varphi
\begin{pmatrix}W+(U-W)s&0\\0&W\end{pmatrix}R_\varphi^{-1},
\qquad 0\le s\le1,\quad\varphi\in\mathbb R/\pi\mathbb Z.
\]
The parameter space is a disk: all angles at $s=0$ give $W I$.
Consider open paths from the seed whose last vertex is their first
exit from $\{|A^{-1}\pi|_2<1\}$. Their final normalized radius is
between $1$ and $1+D_\pi/W$. Seed contact with the infinite cluster
guarantees such a path, since an infinite ray cannot have bounded
projection. Split the exit event according to the $M$ endpoint arcs.
Their misses are decreasing events. Harris's inequality implies that
at least one arc is hit with probability greater than $1-\eta/20$.
Call its center a favored center.
For sufficiently large $U$, every favored center at a boundary
parameter $s=1$ has its unoriented line within angle $\pi/16$ of the
minor axis, uniformly in $\varphi$. Otherwise take $U_j\to\infty$
and boundary parameters violating this assertion. A subsequence of
their major axes converges to a fixed direction $d$. Since the arc
radii are small, favored exits have major-axis displacement bounded
below by a positive constant times $U_j$, while the whole exit path
has transverse displacement at most $W+D_\pi$. Loop erasure gives
arbitrarily long simple open paths from the finite seed. For each
fixed length $l$, all such initial segments lie in the finite union
of radius-$l$ balls about the seed. Convergence of the axes is uniform
on the projections of this finite set. Since $D_\pi<W$, it puts
these segments in the centered strip about $d$ of width $2W$, for
all sufficiently large $j$. Such length-$l$ paths thus have probability at least
$1-\eta/20$ for every $l$. These events decrease with $l$, and finite
branching supplies an infinite ray in the strip, a contradiction.
Triangulate the parameter disk so finely that adjacent matrices
satisfy $\|A_i^{-1}A_j-I\|_2\le\zeta$ and boundary angle increments
are less than $\pi/32$. Choose one favored center at each vertex.
Some adjacent center lines have projective separation at least
$\pi/8$. Indeed, otherwise the principal increments of their doubled
line angles have absolute value less than $\pi/4$. Their sum around
each triangle is a multiple of $2\pi$ of absolute value less than
$2\pi$, hence zero; summing triangles gives zero around the boundary.
On the boundary, however, the doubled angles have lifts
$2\varphi+\pi$ with errors of absolute value less than $\pi/8$.
The mesh condition makes successive lift differences principal
increments, whose total is $2\pi$. This is a contradiction.
\input{figures/moves}
Take such an adjacent pair with matrices $A_i,A_j$. Let $d_1,d_2$
be their signed favored unit arc centers in their respective normalized
coordinates, so $|\det(d_1,d_2)|\ge\sin(\pi/8)$. Let $\Psi$ send
these original centers to $(1,1)$ and $(1,-1)$; its operator norm is
less than $10$. Set $\Phi=\Psi A_i^{-1}$. A point of the second path
with normalized coordinate $u=A_j^{-1}\pi(x)$ has coordinate
$A_i^{-1}A_j u$ under the first matrix. Its displacement from $u$
is at most $\zeta|u|_2$. Thus arc width, radial overshoot, and this
adjacent-matrix error give endpoint error less than $e/8$ once
$D_\pi/W<\zeta$. The whole paths have coordinate displacement less
than $30$, and edge increments tend to zero as $W\to\infty$.
\emph{Case 2: some fixed direction supports a strip ray with positive
probability.} Existence of a ray in some finite-width centered strip
in that direction is a tail event: a suffix survives every finite
edge modification. Its probability is therefore one. Choose a seed
radius $m_0$ and a width $w$ so that a ray from $B(o,m_0)$ in that
strip exists with probability greater than $1-(\eta/30)^2$.
Enlarge $w$ to contain the seed projection as well. Write the
longitudinal and transverse coordinates in these perpendicular axes.
Such a ray is longitudinally unbounded in absolute value, by the
bounded-projection hypothesis.
Choose an arbitrarily large transverse scale $V$ with
$w/V<\zeta$ and $D_\pi/V<\zeta$.
By uniqueness and the preceding directional tail observation, on
the seed-strip event the seed also connects to absolute transverse
level $V$. Stop at the first such crossing. Its finite path can be
confined to some longitudinal bound $M(V)$ while retaining probability
greater than $1-2(\eta/30)^2$: increase the bound and use continuity
from below. Choose $U$ with $M(V)/U<\zeta$ and $D_\pi/U<\zeta$.
The strip ray also gives a
first crossing of absolute longitudinal level $U$ with probability
greater than $1-(\eta/30)^2$.
Split each kind of exit by its sign. Harris's inequality on the two
misses supplies one favored sign of each kind, each with probability
greater than $1-\eta/10$. After division by $U,V$, each endpoint is
within supremum distance $\zeta$ of its signed coordinate unit vector,
and both paths lie in the square $[-2,2]^2$.
A linear map sending those two vectors to $(1,1),(1,-1)$ gives
endpoint error less than $e/8$ and path displacement less than $30$.
For any requested operator bound, first take $V$ sufficiently large,
then determine the finite bound $M(V)$, and finally take $U$ sufficiently
large. The last linear map has norm at most $2$, so the composite map
has norm at most $2/\min(U,V)$. No bound on the growth of $M(V)$ is
needed. Thus edge increments can be made arbitrarily small after
the seed has been fixed.
Let $c$ be a density radius of the orbit $\Lambda o$ and set
$m=m_0+c$. Given $y$, choose $g$ with $d(go,y)\le c$.
Equivariance translates the two events at $o$ to $go$, and their seeds
lie in $B(y,m)$. Include in the preceding scale choices the requirements
$|\Phi\pi(go)-\Phi\pi(y)|_\infty<e/8$ and that edge increments
are at most the requested $\rho_0$: it suffices to make the operator norm
of $\Phi$ smaller than both $e/(8(c+1)D_\pi)$ and $\rho_0/D_\pi$.
The endpoint errors are then at
most $e/4$, and the path bound is less than $100$. All choices of
$m$ preceded the requested small edge increment.
Only now lower the percolation parameter. Finite paths witness the
two events at $o$. Approximate each by a finite union of path witnesses,
preserving a probability greater than $1-\eta$, with room to spare.
Continuity of these finite events gives the same bounds at a common
$p'\in[\pc/2,\pc)$. Their translates give the required bounds at
every $y$ by the preceding deterministic containment.
\end{proof}
==== END No-percolation-at-criticality-on-quasi-transitive-graphs//sections/moves.tex ====
==== BEGIN No-percolation-at-criticality-on-quasi-transitive-graphs//structure.tex ====
\section{Nilpotent quotients and bounded projections}
\label{sec:structure}
The remaining growth case has a polynomial bound along a sequence of
scales. Its useful consequence is an action on the original graph with
a nilpotent quotient. The quotient will supply coordinates; all
percolation paths and edge exposures will remain in the original graph.
We prove the following action theorem and then apply it to the action
constructed from the polynomial scales.
\begin{theorem}[Criticality with a nilpotent quotient action]
\label{thm:structured}
Let $G$ be an infinite connected locally finite graph of subexponential
growth. Suppose a group $\Lambda$ acts by automorphisms on $G$ with
finitely many vertex orbits and admits an epimorphism $\varrho:\Lambda\to N$ onto a
finitely generated nilpotent group, such that $\ker\varrho$ has finite
vertex orbits and $\varrho(\Lambda_v)$ is finite for every vertex $v$.
Here $\Lambda_v=\{g\in\Lambda:gv=v\}$ is the vertex stabilizer.
If $\pc(G)<1$, then
\[
\PP_{\pc(G)}(|C_v|=\infty)=0\qquad(v\in G).
\]
Consequently, critical percolation has almost surely no infinite cluster.
\end{theorem}
The action need not be faithful, and \(\Lambda\) need not itself be
nilpotent. We first show that a polynomial bound along an unbounded
sequence supplies exactly these action data. We then prove the theorem
by induction on a cyclic series of \(N\). In the induction step, a
component over a bounded coordinate box has a quotient with fewer
infinite cyclic factors. This excludes rays with bounded projection;
Sections~\ref{sec:moves} and~\ref{sec:corridor-exploration} use the
remaining rays to construct percolation below \(\pc\).
\subsection{From polynomial scales to the quotient action}
The structural ancestry is Gromov's group theorem \cite{Gromov1981},
Trofimov's graph and near-polynomial growth theorems
\cite{Trofimov1985,Trofimov2003}, and Tessera and Tointon's one-scale
form \cite{TesseraTointon2021}. The proof below uses the latter with
its action and stabilizer conclusions.
\begin{proposition}[The action supplied by a polynomial scale]
\label{prop:nilpotent-model}
Let $G$ be an infinite connected locally finite quasi-transitive graph.
Suppose that for some $d<\infty$ there are radii $R_j\to\infty$ such that
$V_-(R_j)\le R_j^d$. Then there are a finite-index subgroup
$\Lambda\le\operatorname{Aut}(G)$, a finitely generated nilpotent group
$N$, and an epimorphism
\[
\varrho:\Lambda\longrightarrow N
\]
with the following properties:
\begin{enumerate}
\item $\Lambda$ has finitely many vertex orbits;
\item $\ker\varrho$ has finite vertex orbits;
\item $\varrho(\Lambda_v)$ is finite for every vertex $v$, where
$\Lambda_v=\{g\in\Lambda:gv=v\}$.
\end{enumerate}
\end{proposition}
\begin{proof}
Increase $d$ if necessary so that $d\ge1$. Let $C$ be a common density
radius for the finitely many vertex orbits of $\operatorname{Aut}(G)$. Fix one orbit $O$, set $L=2C+1$, and form a
graph $\Gamma$ on $O$ by joining distinct vertices whose distance in $G$
is at most $L$. To connect two points of $O$, take a path between them
in $G$ and replace its intermediate vertices by points of $O$ within
distance $C$. Consecutive replacements are equal or adjacent in
$\Gamma$. Thus $\Gamma$ is connected. It is locally finite, and the
image $A$ of $\operatorname{Aut}(G)$ on $O$ is a transitive subgroup of
$\operatorname{Aut}(\Gamma)$.
At a radius $R=R_j$, choose $x$ with $|B(x,R)|=V_-(R)$ and $u\in O$
with $d(x,u)\le C$. For $n=\lfloor(R-C)/L\rfloor$,
\[
B_\Gamma(u,n)\subseteq B_G(u,Ln)\subseteq B_G(x,R).
\]
Writing $\beta_\Gamma(n)$ for the cardinality of a radius-$n$ ball in
this transitive graph, we obtain $\beta_\Gamma(n)\le R^d$.
For all sufficiently large such scales, $R\le c n$ with a fixed
constant $c$. Absorbing $c^d$ into an extra power of $n$ gives
\[
\beta_\Gamma(n)\le n^{d+1}\beta_\Gamma(1)
\]
for arbitrarily large integers $n$.
Apply Tessera--Tointon's Corollary~2.4 with growth exponent $d+1$,
$\lambda=1/2$, and the transitive group $A$
\cite[Corollary~2.4]{TesseraTointon2021}.
Its hypotheses require only one sufficiently large scale and do not
require $A$ to be closed in $\operatorname{Aut}(\Gamma)$.
The conclusion supplies a normal subgroup $H\lhd A$ whose orbits
have finite diameter, such that $Q=A/H$ acts faithfully on
$\Gamma/H$, is finitely generated and virtually nilpotent, and has
finite vertex stabilizers. The $H$-orbits are finite because $\Gamma$
is locally finite.
Let $\vartheta:\operatorname{Aut}(G)\to Q$ be the composite
epimorphism, and put $K=\ker\vartheta$. Its orbits on $O$ are the
$H$-orbits. For an arbitrary $v\in G$, choose $u\in O$ with
$d(u,v)\le C$. Then
\[
Kv\subseteq\bigcup_{w\in Ku}B_G(w,C),
\]
so $Kv$ is finite. Also, $\operatorname{Aut}(G)_v$ moves $u$ within
the finite ball $B_G(v,C)$. Hence its image under $\vartheta$ has a
finite orbit on the block $H(u)\in\Gamma/H$. Its stabilizer at that
block is a subgroup of the finite $Q$-stabilizer. The orbit--stabilizer
formula therefore makes $\vartheta(\operatorname{Aut}(G)_v)$ finite.
Choose a finite-index nilpotent subgroup $N\le Q$ and let
$\Lambda=\vartheta^{-1}(N)$. A finite-index subgroup of a finitely
generated group is finitely generated: rewriting a word through a
finite set of coset representatives gives a finite generating set.
Thus $N$ is finitely generated. Each $\operatorname{Aut}(G)$-orbit
splits into at most $[\operatorname{Aut}(G):\Lambda]$ many
$\Lambda$-orbits. Restricting $\vartheta$ to $\Lambda$ gives
$\varrho$, with the other two properties already proved.
\end{proof}
\subsection{Cyclic series and the decreasing parameter}
A \emph{cyclic series} is a finite subnormal series
\[
N=N_0\triangleright N_1\triangleright\cdots\triangleright N_k=\{1\}
\]
whose factors $N_i/N_{i+1}$ are cyclic, possibly finite or trivial.
We use the number of its infinite factors. The induction applies to
all data equipped with a chosen series of at most a given count;
independence of that count from the choice of series is not needed.
The group facts below are classical; see
\cite[Theorems~5.2.5 and~5.2.18]{Robinson1996}.
We give the arguments to make the decrease of the induction parameter
explicit.
\begin{lemma}[Cyclic series and their subgroups]
\label{lem:rank}
Every finitely generated nilpotent group $N$ has a cyclic series.
If such a series has $h$ infinite factors, then every subgroup $J\le N$
is finitely generated and inherits a cyclic series with at most $h$
infinite factors. If $[N:J]=\infty$, the inherited count is strictly
less than $h$.
Moreover, if the finitely generated abelianization $N/[N,N]$ has rank
at most one, then $[N,N]$ is finite. In this case $N$ is either finite
or admits an epimorphism onto $\mathbb Z$ with finite kernel.
\end{lemma}
\begin{proof}
Write $\gamma_1=N$ and $\gamma_{i+1}=[N,\gamma_i]$ for the lower
central series. The first factor $N/\gamma_2$ is finitely generated
abelian. Modulo $\gamma_{i+2}$, the commutator product identities give
a bilinear map
\[
(N/\gamma_2)\times(\gamma_i/\gamma_{i+1})
\longrightarrow\gamma_{i+1}/\gamma_{i+2},
\qquad (x\gamma_2,y\gamma_{i+1})\longmapsto[x,y]\gamma_{i+2},
\]
whose values generate the target. Here bilinearity follows because
commutators of one higher weight vanish in the target quotient.
Inductively, images of pairs of finite generating sets generate each
successive factor. These factors are abelian, and nilpotence makes
only finitely many of them nontrivial. Refining each finitely generated
abelian factor by adjoining its generators one at a time gives a
cyclic series.
For a subgroup $J$, intersect this series with $J$. The natural map
\[
(J\cap N_i)/(J\cap N_{i+1})\longrightarrow N_i/N_{i+1}
\]
is injective, so each inherited factor is cyclic. Lifting generators
successively up this finite series shows that $J$ is finitely generated.
Suppose its count of infinite factors is still $h$. Then its image in
every infinite cyclic ambient factor is infinite, hence has finite
index; its image in a finite factor also has finite index. Induction
up the series gives $[N:J]<\infty$. Explicitly, if
$J_i=J\cap N_i$, then
\[
[J_iN_{i+1}:J_i]=[N_{i+1}:J\cap N_{i+1}],
\]
and $[N_i:J_iN_{i+1}]$ is the index of the image in the cyclic factor.
Both indices are finite at each step, starting from the trivial last
group. This proves the strict decrease for infinite-index subgroups.
For the last assertion, the first commutator pairing is alternating
on $N/\gamma_2$. If that abelian group has rank at most one, the
pairing has only torsion values: its exterior square is a finitely
generated torsion group. Its finitely many generating values make
$\gamma_2/\gamma_3$ finite. The displayed bilinear pairing then makes every later factor
finite as well. Thus $[N,N]=\gamma_2$ is finite. Rank zero of the
abelianization makes $N$ finite. In rank one, projection of the
abelianization onto its infinite cyclic factor gives an epimorphism
$N\to\mathbb Z$ with finite kernel.
\end{proof}
\subsection{The induction and equivariant coordinates}
Fix action data \((G,\Lambda,\varrho,N)\) as in
Theorem~\ref{thm:structured}, together with a cyclic series having
\(h\) infinite factors. We prove the theorem simultaneously for all
such data by induction on \(h\). A series with no infinite factor
makes \(N\) finite. Each $\Lambda$-orbit is a finite union of
$\ker\varrho$-orbits and is therefore finite. There are finitely
many $\Lambda$-orbits, contrary to infinitude of $G$.
This is the base case. For the induction step, assume the theorem
for every such action whose quotient has a cyclic series with fewer
than \(h\) infinite factors. Suppose, towards a contradiction, that
\(\pc(G)<1\) and critical percolation has an infinite cluster with
positive probability.
We first construct the coordinates and dispose of the one-dimensional
case. Suppose $\phi:N\to\mathbb Z^j$ is an epimorphism, where $j=1$ or $2$.
Choose representatives $v_1,\ldots,v_k$ for the $\Lambda$-orbits and
put
\begin{equation}\label{eq:equivariant-projection}
\pi(gv_i)=\phi\varrho(g),\qquad g\in\Lambda.
\end{equation}
This is well defined: if $gv_i=g'v_i$, then $(g')^{-1}g$ stabilizes
$v_i$, its $\varrho$-image belongs to a finite group, and $\phi$
annihilates that image because $\mathbb Z^j$ is torsion free. Moreover,
\begin{equation}\label{eq:projection-equivariance}
\pi(gx)=\phi\varrho(g)+\pi(x).
\end{equation}
The map is onto, even on each vertex orbit. There are finitely many
oriented edge orbits, so equivariance gives a finite bound
\begin{equation}\label{eq:projection-edge-bound}
D_\pi:=\sup_{x\sim y}|\pi(x)-\pi(y)|<\infty.
\end{equation}
The norm is Euclidean when $j=2$.
Suppose that $\phi:N\to\mathbb Z$ has finite kernel.
Then $L_0=\ker(\phi\varrho)$ has finite orbits: its image under
$\varrho$ is finite, and its kernel has finite orbits. Thus
\[
\pi^{-1}(0)=\bigcup_{i=1}^k L_0v_i
\]
is finite. An element with $\phi\varrho$-value $t$ bijects this level
onto $\pi^{-1}(t)$, so all integer levels have the same finite size.
Choose an integer $J\ge\max(1,D_\pi)$. Edges crossing the cut from
$\{\pi\le t\}$ to $\{\pi>t\}$ have endpoints in a fixed number of
levels around $t$. Their number is uniformly bounded, since degree
and level sizes are bounded. The crossing-edge sets for levels
$t\in(J+1)\mathbb Z$ are disjoint. For every $p<1$, their all-closed
events are independent with probabilities bounded below by a positive
constant. Almost surely infinitely many such cuts are closed in both
directions. Every open cluster is then confined between two closed
cuts and lies in finitely many finite levels. This proves
\begin{equation}\label{eq:cyclic-critical-one}
\pc(G)=1
\quad\text{whenever $N$ has an epimorphism to $\mathbb Z$
with finite kernel.}
\end{equation}
Consequently, the hypotheses of Theorem~\ref{thm:structured} with
$\pc(G)<1$ force the abelianization of $N$ to have rank at least two.
It therefore admits an epimorphism onto $\mathbb Z^2$.
\subsection{Excluding rays with bounded projection}
We now choose an epimorphism \(\phi:N\to\mathbb Z^2\), as justified
above, and let \(\pi\) be the associated coordinate map. The smaller-count
induction applies to a component over a bounded box because its
preserving subgroup maps into \(\ker\phi\), an infinite-index subgroup
of \(N\). The next lemma checks all the required action properties.
\begin{lemma}[Exclusion of bounded projections]
\label{lem:bounded-projection}
\label{lem:unbounded-projection}
Let $(G,\Lambda,\varrho,N)$ satisfy the hypotheses of
Theorem~\ref{thm:structured}, with $\pc(G)<1$. Fix a cyclic series for
$N$ with $h$ infinite factors and an epimorphism $\phi:N\to\mathbb Z^2$.
Let $\pi$ be given by \eqref{eq:equivariant-projection}. Assume
Theorem~\ref{thm:structured} for every such action whose nilpotent
quotient has a cyclic series with fewer than $h$ infinite factors.
Then critical percolation on $G$ almost surely has no infinite open ray
whose $\pi$-projection is bounded.
\end{lemma}
\begin{proof}
Suppose otherwise. There are countably many finite boxes in
$\mathbb Z^2$ and countably many connected components of their inverse
images. Hence some fixed finite box $Q$ and a fixed infinite connected
component $G'$ of the induced graph $G[\pi^{-1}(Q)]$ have an infinite
open cluster at $p=\pc(G)$ with positive probability. Subgraph
monotonicity gives $\pc(G')\ge\pc(G)$; this positive probability
gives the reverse inequality. Thus
\[
\pc(G')=\pc(G)<1,
\]
and $G'$ percolates at its own critical value.
Let $\Lambda'$ consist of the elements of $\ker(\phi\varrho)$ that
preserve $G'$. It has finitely many vertex orbits on $G'$. Indeed,
if $x,y\in G'$ lie in the same $\Lambda$-orbit and satisfy
$\pi(x)=\pi(y)$, choose $g\in\Lambda$ with $gx=y$.
Equation~\eqref{eq:projection-equivariance} gives
$\phi\varrho(g)=0$. This element preserves the induced graph
$G[\pi^{-1}(Q)]$ and maps the component of $x$ to that of $y$;
these are the same component. Thus $g\in\Lambda'$. There are only
finitely many pairs of an original $\Lambda$-orbit and a level in $Q$,
which proves the claim.
Set $N'=\varrho(\Lambda')$. Restriction gives an epimorphism
$\Lambda'\to N'$ whose kernel has finite orbits and whose vertex
stabilizers have finite images. The group $N'$ is nilpotent and is
finitely generated by Lemma~\ref{lem:rank}. It lies in $\ker\phi$,
which has infinite index in $N$, so its inherited cyclic series has
strictly fewer than $h$ infinite factors. The graph $G'$ is connected,
locally finite and infinite. Its intrinsic balls are contained in
ambient balls of the same radius, so it has subexponential growth.
It therefore satisfies every hypothesis of the smaller-count
induction. Theorem~\ref{thm:structured} at that count forbids the
critical infinite cluster just found, a contradiction.
\end{proof}
Thus the induction step has onto equivariant coordinates in
\(\mathbb Z^2\), bounded coordinate jumps, and no infinite open ray
trapped over a bounded set. The following two sections construct an
infinite cluster at a parameter below \(\pc(G)\) from the assumed
critical jump. That contradiction completes the induction and proves
Theorem~\ref{thm:structured}. Proposition~\ref{prop:nilpotent-model}
then applies it to the remaining growth case.
==== END No-percolation-at-criticality-on-quasi-transitive-graphs//structure.tex ====
==== BEGIN No-percolation-at-criticality-on-quasi-transitive-graphs//superpolynomial.tex ====
\section{Subexponential growth faster than every power}
\label{sec:superpolynomial}
The interpolation estimate completes the first subexponential branch.
We will find two large distinct clusters at distance whose logarithm
is negligible compared with the logarithm of their sizes. Interpolation
then places them across a single edge at a probability incompatible
with Proposition~\ref{prop:two-cluster}.
\begin{theorem}\label{thm:superpoly}
Let $G$ be an infinite connected locally finite quasi-transitive graph
with $\pc<1$. Suppose that
\[
\log V_+(r)=o(r),
\qquad \frac{\log V_-(r)}{\log r}\longrightarrow\infty.
\]
Then critical Bernoulli bond percolation on $G$ has almost surely no
infinite cluster.
\end{theorem}
\begin{proof}
Suppose instead that critical percolation has an infinite cluster with
positive probability. Let $\theta>0$ be the uniform lower bound in
\eqref{eq:uniform-jump}, and let $D$ be the maximum degree.
By \eqref{eq:positive-threshold}, $\pc>0$.
All constants below may depend on $G$ and $\theta$, but will be
independent of the scales and of $p\in[\pc/2,\pc)$.
\paragraph{A band of finite cluster sizes.}
Choose an arbitrarily large integer $L\ge2$. The event
$\{|C_v|\ge L\}$ is determined by a finite ball: if a cluster has
at least $L$ vertices, a rooted spanning exploration finds $L$ of them
within distance $L-1$ of $v$. Finite-event continuity and the finitely
many orbits therefore allow a single $p\in[\pc/2,\pc)$ for which
\[
F_L(v):=\PP_p(|C_v|\ge L)\ge3\theta/4
\qquad\text{for every }v.
\]
All clusters at this $p$ are finite almost surely. We seek a size
$s\ge L$ at which every vertex still has cluster-tail probability at
least $\theta/2$, while some vertex has a cluster in the band
$[s,s^2)$ with probability at least $(\log s)^{-2}$. The first condition
will force connections between nearby vertices; the second will supply
a finite cluster small enough to find another large cluster nearby.
Set $s_j=L^{2^j}$. The bands $[s_j,s_j^2)$ are disjoint, and the required
lower bounds $(\log s_j)^{-2}$ have a summable total. Let $k\ge1$ be
the first index for which
$F_{s_k}(z)<\theta/2$ for some orbit representative $z$.
Such an index exists because the finite-cluster tails decrease to zero.
For this $z$,
\[
\sum_{j=0}^{k-1}\PP_p(s_j\le |C_z|<s_j^2)
=F_L(z)-F_{s_k}(z)>\theta/4.
\]
On the other hand,
$\sum_{j\ge0}(\log s_j)^{-2}=4/(3(\log L)^2)<\theta/4$
when $L$ is sufficiently large. Hence there are $j<k$ and $s=s_j$
such that
\begin{equation}\label{eq:superpoly-band}
f:=\PP_p(s\le |C_z|<s^2)\ge(\log s)^{-2},
\qquad F_s(v)\ge\theta/2\quad\text{for every }v.
\end{equation}
In particular $s\to\infty$ as $L\to\infty$.
\paragraph{A nearby pair of large distinct clusters.}
Let $r$ be the least integer with $V_-(r)\ge s^4$.
Such an integer exists: an infinite connected locally finite graph has
vertices at every distance from each vertex, so $V_-(r)\ge r+1$.
The growth hypothesis implies
\begin{equation}\label{eq:superpoly-radius}
\log r=o(\log s).
\end{equation}
Indeed, for every fixed $M>0$, eventually $V_-(t)\ge t^M$.
If $r-1$ is beyond this threshold, minimality gives
$(r-1)^M\le V_-(r-1)<s^4$, so $r<1+s^{4/M}$.
The alternative that $r-1$ remains below the threshold only improves
the bound. Letting $M$ be arbitrarily large proves
\eqref{eq:superpoly-radius}.
Condition on an exact incidence exposure of a band cluster
$K=C_z$, with $s\le|K|<s^2$. Its exterior has independent product law.
Resample all incidence edges of $K$ independently with parameter $p$,
leaving the exterior unchanged. For every fixed such exposure, the
resampled full configuration has law $\PP_p$, so the expected number
of vertices in $B(z,r)$ belonging to clusters of size at least $s$
in that configuration is at least
$(\theta/2)|B(z,r)|$.
In the exterior graph $G\setminus K$, at most
\[
|K|+D|K|(s-1)\le s^2+Ds^3
\]
vertices lie in $K$ or in exterior clusters of size less than $s$
that are adjacent to $K$. Every vertex whose resampled cluster has
size at least $s$, but whose exterior cluster has size less than $s$,
lies in this set: otherwise its exterior cluster is unaffected by
resampling incidence edges of $K$. Consequently, uniformly in the
fixed band exposure, the expected number of vertices of $B(z,r)$
in exterior clusters of size at least $s$ is at least
\[
(\theta/2)|B(z,r)|-s^2-Ds^3
\ge(\theta/4)|B(z,r)|
\]
for sufficiently large $L$, because $|B(z,r)|\ge s^4$.
In the original configuration these exterior clusters are distinct
from $C_z=K$. Averaging over the band event and then over $B(z,r)$
therefore gives a deterministic $y\in B(z,r)$ such that
\[
\PP_p(C_y,C_z\text{ distinct},\ |C_y|,|C_z|\ge s)
\ge(\theta/4)f.
\]
Put $c_0=\theta^2/8$, and choose the smallest distance $d$ of any pair
$x,z'$ satisfying
\begin{equation}\label{eq:superpoly-separated-pair}
\PP_p(C_x,C_{z'}\text{ distinct},\ |C_x|,|C_{z'}|\ge s)
\ge c_0 f.
\end{equation}
The preceding pair shows that $d\le r$. Distinct clusters rule out
$d=0$. Proposition~\ref{prop:two-cluster} rules out $d=1$ for all
sufficiently large $L$, since its uniform bound $Cs^{-1/2}$ is smaller
than $c_0(\log s)^{-2}$.
For any pair $u,v$ at distance less than $d$, Harris's inequality and
\eqref{eq:superpoly-band} give probability at least $\theta^2/4$ that
both cluster sizes are at least $s$. By the minimality of $d$, the
probability that they are also distinct is less than $c_0f\le c_0$.
Thus
\begin{equation}\label{eq:superpoly-short-connections}
\PP_p(u\leftrightarrow v)\ge\theta^2/8
\qquad(d_G(u,v)<d).
\end{equation}
\paragraph{A finite graph to which interpolation applies.}
Fix a geodesic from $x$ to $z'$ of length $d$. We now choose a finite
induced ball $F$ sufficiently large; the parameter $p$, size $s$,
pair, and path remain fixed during this choice.
First include the balls of radius $s$ around $x,z'$. Every configuration
in the infinite-graph event \eqref{eq:superpoly-separated-pair} then
has two distinct endpoint clusters of size at least $s$ in $F$ as
well: the size witnesses lie in those balls, and restriction cannot
join distinct clusters. Therefore the finite endpoint-event probability
$\delta_F$ satisfies the exact lower bound
\begin{equation}\label{eq:superpoly-finite-endpoints}
\delta_F\ge c_0f.
\end{equation}
No limiting equality or loss in this bound is needed.
For each proper pair on the geodesic, its path-index separation is
less than $d$, so \eqref{eq:superpoly-short-connections} applies.
Connections in increasing finite induced balls increase to the full
event, since every witnessing path is finite. There are only finitely
many pairs, so enlarge $F$ until their finite-graph connection
probabilities are all at least $\theta^2/16$.
Finally, all clusters at this fixed subcritical $p$ are finite almost
surely. Enlarge $F$ further until, for each edge $e$ of the fixed
geodesic, the probability that either full endpoint cluster is not
contained in $F$ is at most $s^{-1}$. If both clusters are contained,
their restrictions equal the original clusters. Hence
\begin{equation}\label{eq:superpoly-finite-edge-error}
\PP_p^F(H_s(e))
\le\PP_p(H_s(e))+s^{-1}
\le Cs^{-1/2}+s^{-1}
\end{equation}
for every path edge. Enlarging $F$ preserves the earlier endpoint
and connection bounds.
Apply Proposition~\ref{prop:interpolation} in $F$ with
$c=\theta^2/16$. Its constants are uniform: $p\ge\pc/2>0$ and
$1-p\ge1-\pc>0$. By \eqref{eq:superpoly-band},
\eqref{eq:superpoly-radius}, and
\eqref{eq:superpoly-finite-endpoints}, some path edge satisfies
\[
-\log\PP_p^F(H_s(e))
\le C'\bigl(\log(1/(c_0f))+\log r+1\bigr)
\le C'\bigl(2\log\log s+\log r+C''\bigr)
=o(\log s).
\]
But \eqref{eq:superpoly-finite-edge-error} gives
\[
-\log\PP_p^F(H_s(e))
\ge\tfrac12\log s-\log(C+1)
\]
for $s\ge1$, a contradiction as $L\to\infty$.
This proves the theorem.
\end{proof}
==== END No-percolation-at-criticality-on-quasi-transitive-graphs//superpolynomial.tex ====
==== BEGIN No-percolation-at-criticality-on-quasi-transitive-graphs//two-cluster-dfs-entropy.tex ====
\section{Two clusters, depth-first search, and entropy}
\label{sec:dfs-entropy}
The interpolation argument will join clusters along a short path while
controlling the change in probability. We prepare its three inputs: a
bound on adjacent large distinct clusters, a second-moment estimate for
depth-first pivotal edges, and an entropy bound for several explorations
of the same configuration.
\subsection{Adjacent large distinct clusters}
For an edge $e=xy$ and an integer $s\ge1$, write
\[
H_s(e)=\{C_x\ne C_y,\ |C_x|\ge s,\ |C_y|\ge s\}.
\]
Cluster size means the number of vertices. The next estimate is uniform
over the edges, including those in different automorphism orbits.
Its proof adapts the cluster-boundary discrepancy argument of
Aizenman, Kesten, and Newman \cite[Section~3]{AizenmanKestenNewman1987}
and Hutchcroft's ghost-field and martingale formulation
\cite[Section~3]{Hutchcroft2020Locality}.
We give the finite-graph averaging argument and its quasi-transitive
passage explicitly.
\begin{proposition}\label{prop:two-cluster}
Let $G$ be an infinite connected locally finite quasi-transitive graph
of subexponential growth. For every $p_*>0$ there is $C<\infty$ such
that
\[
\PP_p(H_s(e))\le C s^{-1/2}
\qquad(e\in E(G),\ s\ge1,\ p_*\le p<1).
\]
The constant may depend on $G$ and $p_*$.
\end{proposition}
\begin{proof}
Let $D$ bound the degrees of $G$. We first prove an averaged estimate
on any finite induced subgraph $F$. Independently of the edge states,
mark each vertex with probability $1-e^{-h}$, where $0<h\le1$.
Let $T_e$ be the event that the endpoints of $e$ lie in distinct clusters
both containing a mark. Let $N_e$ count the marked clusters incident
to $e$, counting a cluster only once even when it contains both endpoints,
and put $I_e=\mathbf1_{\{N_e\ge1\}}$. Flipping $e$ does not change the
union of its endpoint clusters, so $I_e$ is unchanged by that flip.
For closed $e$, $\mathbf1_{T_e}=N_e-I_e$, whereas for open $e$,
$N_e=I_e$. With $q=1-p$, conditioning on all other edges therefore gives
\begin{equation}\label{eq:marked-cluster-discrepancy}
\sum_{e\in E(F)}\PP_p(T_e)
=\EE_p\sum_{K\text{ marked cluster}}
\left(c(K)-\frac qp\,o(K)\right),
\end{equation}
where $c(K)$ and $o(K)$ count the closed and open edges incident to $K$,
respectively. Each incidence is counted once per cluster.
Explore a cluster $C_v$, querying all its incident edges, including
internal edges, once each. If $T$ is the number of queries and
$m=|C_v|$, then $T\le Dm$ and, when $T>0$, $m\le T+1\le2T$.
The fresh query bits are independent Bernoulli variables of parameter
$p$; after stopping, extend them with independent auxiliary bits.
Let $Z_j$ be their centered partial sums. Since
$o(C_v)$ is the number of open query bits,
\[
c(C_v)-\frac qp o(C_v)=-\frac1p Z_T.
\]
Rewrite the sum over clusters in
\eqref{eq:marked-cluster-discrepancy} as a sum over vertices, dividing
the summand by the cluster size. Averaging the marks and taking absolute
values gives
\begin{equation}\label{eq:marked-average-bound}
\frac1{|V(F)|}\sum_e\PP_p(T_e)
\le\frac Dp\max_{v\in V(F)}
\EE_p\left[\frac{|Z_T|}{T}\min\{2hT,1\}\right],
\end{equation}
with value zero when $T=0$.
Doob's maximal inequality yields
\[
\EE_p\max_{j\le 2^{k+1}}|Z_j|
\le2\sqrt{pq\,2^{k+1}}.
\]
Partitioning according to $2^k\le T<2^{k+1}$, the expectation in
\eqref{eq:marked-average-bound} is at most
\[
C_0\sqrt{pq}\sum_{k\ge0}2^{-k/2}
\min\{2^{k+2}h,1\}
\le C_1\sqrt{pq}\sqrt h.
\]
For the last bound, split the sum where $2^kh$ first exceeds one;
both resulting geometric series are bounded by a constant times
$\sqrt h$. On $H_s(e)$, conditional on the edges, the two clusters
are marked with probability at least $(1-e^{-hs})^2$. Taking $h=1/s$
therefore proves
\begin{equation}\label{eq:finite-two-cluster-average}
\sum_{e\in E(F)}\PP_p^F(H_s(e))
\le C_2|V(F)|s^{-1/2},
\end{equation}
uniformly for $p\ge p_*$.
To pass to an individual edge, choose $C_0'$ so that every vertex orbit
is $C_0'$-dense. Fix an edge $e=xy$ and a center $o$. For every vertex
of $B(o,n)$, choose a point in the orbit of $x$ within distance $C_0'$.
There are at least $|B(o,n)|/V_+(C_0')$ distinct chosen points. At each,
an automorphic copy of $e$ has both endpoints in $B(o,n+C_0'+1)$.
Each unoriented edge is counted at most twice, so the number of distinct
copies is at least
\[
\frac{|B(o,n)|}{2V_+(C_0')}.
\]
For fixed $s$, subexponential growth gives arbitrarily large $n$ with
\[
|B(o,n+C_0'+s+1)|\le2|B(o,n)|.
\]
Otherwise iteration of this fixed-width expansion would force
exponential growth. Set $F=G[B(o,n+C_0'+s+1)]$. A connected cluster
with at least $s$ vertices has a connected $s$-vertex witness within
distance $s-1$ of any specified vertex. Thus $H_s$ in the full graph
implies $H_s$ in $F$ for each selected copy; restriction also preserves
distinctness. All copies have the same full-graph probability.
Apply \eqref{eq:finite-two-cluster-average} and the displayed bounds
to obtain the proposition. The constants do not depend on the orbit
of $e$.
\end{proof}
\subsection{Clusters conditioned to avoid one another}
Conditional association of connection events was established by
van den Berg and Kahn \cite{VanDenBergKahn2001}.
The pivotal estimate uses the cluster-function correlation inequality of
van den Berg, H\"aggstr\"om, and Kahn
\cite[Theorems~1.3 and~1.4]{VanDenBergHaggstromKahn2006}. We include the
product-measure proof by alternating cluster updates, the method of
\cite[Section~2.1]{VanDenBergHaggstromKahn2006}.
Here a cluster object records its vertices and all its open edges.
For a root set, take the union of the cluster objects of its roots.
Objects are ordered by inclusion of both vertices and edges.
A random object is \emph{associated} if any two increasing real-valued
functions of it have nonnegative covariance.
\begin{lemma}[Avoidance correlation]\label{lem:avoidance}
Let $G$ be a finite undirected graph with independent edge probabilities
strictly between zero and one. Let $A,B$ be disjoint nonempty vertex
sets. Conditional on $A\not\leftrightarrow B$, each of the two cluster
objects $C(A)$ and $C(B)$ is associated. If $f$ and $g$ are increasing
functions of the respective objects, then
\[
\Cov\bigl(f(C(A)),g(C(B))\mid A\not\leftrightarrow B\bigr)\le0.
\]
\end{lemma}
\begin{proof}
Given one exact object under avoidance, the other has its ordinary
product-cluster law after deleting the first object's vertices.
Indeed, the exact object fixes its open internal edges, its closed
internal edges, and its closed boundary edges; all edges wholly outside
it retain their independent laws. Avoidance is then automatic.
By restriction of a common configuration, this conditional law is
stochastically decreasing as the deleted object grows.
Start with a deterministic admissible object at $A$, sample the object
at $B$ by this conditional law, then update the object at $A$ in the
same manner, and repeat. Association is preserved at every half-step.
To see this, conditional on the current object, the next object is an
increasing function of independent bits and is associated by Harris's
inequality. The two conditional means of increasing functions of the
next object are decreasing functions of the current object. Their
covariance is nonnegative when the current object is associated.
The conditional covariance identity proves the assertion.
The two-step chain on the $A$ objects has the avoidance marginal as
a stationary law, because its updates are the two conditional laws of
that joint distribution. Every transition has a common positive mass
at the minimal object consisting of $A$ and no open edges: close all
edges incident to $A$ in its update. This probability is bounded below
by the product of the closed-edge probabilities over all edges of $G$.
Subtracting that common mass from every transition shows that total
variation distances contract by a factor strictly less than one.
Consequently the chain converges to its stationary law. Association
passes to this finite-state limit, proving association of $C(A)$;
the same argument applies to $C(B)$.
Finally, the conditional mean of $g(C(B))$ given $C(A)$ is decreasing
in $C(A)$. Association of the latter object makes its covariance with
the increasing function $f(C(A))$ nonpositive. Taking conditional
expectations proves the claimed cross covariance.
\end{proof}
\subsection{A depth-first pivotal second moment}
Fix a finite undirected graph, a vertex $w$, and a deterministic target
set $B$. Write $E=\{w\leftrightarrow B\}$ and let $\mu$ be homogeneous
Bernoulli percolation with parameter $0<p<1$, with $q=1-p$.
Parallel edges are allowed. We use the following deterministic lazy
depth-first search. On reaching a vertex, push its unqueried edges to
unreached vertices onto a stack in a fixed order. Pop the last entry;
if its head has meanwhile been reached, skip it without reading its
bit. Otherwise query the bit, reaching its head when it is open.
Stop on reaching $B$ or exhausting the stack.
A \emph{query prefix} records the previously queried edges and their
states. At a query of $e$, put
\[
h=\mu(E\mid\text{prefix}),\qquad
h_b=\mu(E\mid\text{prefix},X_e=b),\qquad d_e=h_1-h_0.
\]
These probabilities condition only on that search's own query prefix.
They are not conditioned on any additional cluster information that
another construction may possess. Since $E$ is increasing, $0\le d_e\le1$.
A queried edge is an \emph{actual open pivot} if it is open and closing
it destroys $E$ in the full configuration, including unqueried edges.
\begin{lemma}\label{lem:dfs}
For the preceding search, let
\[
W=\sum_{e\text{ queried actual open pivot}}q d_e.
\]
Then $\EE_\mu W\le1$ and $\EE_\mu W^2\le3$.
\end{lemma}
\begin{proof}
The claim is immediate if $w\in B$ or $B=\varnothing$.
The conditional probabilities of $E$ form a martingale along the
search. At a query its conditional variance increment is $pq d_e^2$.
The search decides $E$, so
\begin{equation}\label{eq:dfs-variance-budget}
\EE_\mu\sum_{e\text{ queried}}pq d_e^2
=\Var_\mu(\mathbf1_E)\le1.
\end{equation}
Given the pre-query prefix, the probability of an actual open pivot is
$p d_e$. Thus \eqref{eq:dfs-variance-budget} equals $\EE W$.
It also bounds the diagonal terms in $\EE W^2$, since
$p d_e(qd_e)^2\le pq d_e^2$.
It remains to bound the products of weights from two pivots. We prove
the following conditional estimate for each earlier query $f$:
\begin{equation}\label{eq:dfs-future-pair-bound}
\EE\left[
\mathbf1_{\{f\text{ actual pivot}\}}
\sum_{e\text{ later actual open pivot}}q d_e
\,\middle|\,\text{prefix of }f,\ f\text{ open}\right]\le d_f.
\end{equation}
Its right side is the pivotal probability before reading $f$.
Multiplying by the probability $p$ that $f$ is open and by its weight
$qd_f$ will bring the pair sum back within the variance budget
\eqref{eq:dfs-variance-budget}.
Fix this prefix and condition on $f$ being open, with new head $z$.
If $z\in B$ there are no later queries. Otherwise contract the vertices
reached before $f$ to a root $A$ and delete $f$ for the connectivity
calculations that follow. Those vertices are connected by known open
edges and contain no target vertex. If $f$ is an actual pivot, $z$
connects to $B$ without using $A$, while $A$ does not connect to $B$.
The depth-first subsearch from $z$ then succeeds before any older stack
entry is resumed. We call this subsearch, stopped on success or
exhaustion, the \emph{phase}.
At a query $e$ in the phase, contract its already reached vertices to
$S$, containing $z$, and wire $B$ to one target vertex. Keep $A$ and
$S$ separate: their only known open link before deletion was $f$.
Delete queried closed edges. All unqueried edges remain independent,
including older stack edges whose endpoints may now lie in $A$ and
$S$. Whether still pending or already skipped, they have not been tested.
The tail of $e$ lies
in $S$ and its head $b$ is unreached.
In this residual product graph with $e$ held closed, let
\[
\begin{array}{c|cccc}
\text{connectivity of }A,S,B
&\text{all separate}&SB\text{ only}&AB\text{ only}&AS\text{ only}\\ \hline
\text{probability}&u&v&v_A&x.
\end{array}
\]
The remaining possibility is that all three are connected. Define
\[
\begin{aligned}
\alpha&=\PP(\text{all separate},\ b\leftrightarrow B),&
\beta&=\PP(\text{all separate},\ b\leftrightarrow A),\\
\gamma&=\PP(SB\text{ only},\ b\leftrightarrow A),&
\sigma&=\PP(AS\text{ only},\ b\leftrightarrow B).
\end{aligned}
\]
Here and until the next conditioning all probabilities refer to the
unqueried product bits with $f,e$ deleted. In the actual search $f$
is open, so $A$ and $S$ are wired together when computing $d_e$.
Consequently
\begin{equation}\label{eq:dfs-partition-pivots}
d_e=\alpha+\sigma,
\qquad
\PP(f,e\text{ both actual open pivots}\mid\text{prefix},f\text{ open})
=p\alpha.
\end{equation}
Indeed, opening $e$ joins the wired source to the target exactly in
the $\alpha$ or $\sigma$ cases. In the second case $A$ was already
connected to $S$ without $f$, so $f$ is not pivotal; the first case
gives both pivots.
Apply Lemma~\ref{lem:avoidance} with root sets $A$ and $S\cup B$,
using the increasing events $b\leftrightarrow A$ and
$S\leftrightarrow B$ in their respective cluster objects. It gives
$\gamma u\le v\beta$. Reversing the roles, with roots $B$ and
$A\cup S$, gives $\sigma u\le x\alpha$. The two decreasing isolation
events $A\not\leftrightarrow S\cup B$ and
$B\not\leftrightarrow A\cup S$ have intersection of probability $u$.
Harris's inequality therefore gives
\begin{equation}\label{eq:dfs-isolation-inequalities}
\gamma u\le v\beta,
\qquad \sigma u\le x\alpha,
\qquad u\ge(u+v)(u+x).
\end{equation}
In particular, when $u>0$,
\begin{equation}\label{eq:dfs-pivotal-comparison}
d_e\le\alpha\frac{u+x}{u}\le\frac\alpha{u+v}.
\end{equation}
The open-edge information in the cluster objects matters here:
the union of the root vertices alone does not determine
$S\leftrightarrow B$.
We now pay for these later pivotal weights with a second martingale.
An actual pivot $f$ requires the old root $A$ to avoid both $z$ and the
target. Accordingly, for the rest of the phase condition the deleted-$f$
configuration on the fixed event
\[
U=\{A\not\leftrightarrow\{z,B\}\}.
\]
Let $U_{\rm init}$ be its probability at the beginning of the phase.
If it is zero, no pair involving an actual pivot $f$ contributes.
Otherwise, under this conditioned law, let $r$ be the conditional
probability of $z\leftrightarrow B$ along the phase. This is a
bounded martingale even though its query bits are no longer Bernoulli
with parameter $p$.
At the current prefix write $U_0,U_1$ for the probabilities of $U$
when $e$ is closed and open. The partition above gives
\[
U_0=u+v,\qquad U_1=U_0-\beta-\gamma,
\qquad U_{\rm pre}=qU_0+pU_1.
\]
The corresponding probabilities of $U\cap\{z\leftrightarrow B\}$
are $v$ and $v+\alpha-\gamma$. Hence, whenever $U_1>0$,
\begin{equation}\label{eq:dfs-tilted-increment}
r_1-r_0
=\frac{U_0\alpha+v\beta-u\gamma}{U_0U_1}
\ge\frac\alpha{U_1}.
\end{equation}
The conditional bit probabilities under the tilt are
$pU_1/U_{\rm pre}$ and $qU_0/U_{\rm pre}$.
Bayes's formula multiplies the ordinary probability of this prefix by
$U_{\rm pre}/U_{\rm init}$. Thus, after multiplying the tilted
martingale variance budget by $U_{\rm init}$, its contribution at
this prefix, expressed under the ordinary phase law, is
\[
pq\frac{U_0U_1}{U_{\rm pre}}(r_1-r_0)^2.
\]
If $\alpha>0$, then $u>0$ and $U_1\ge\alpha>0$; moreover
$U_1,U_{\rm pre}\le U_0$. Equations
\eqref{eq:dfs-tilted-increment} and
\eqref{eq:dfs-pivotal-comparison} therefore give
\begin{equation}\label{eq:dfs-converted-budget}
pq\frac{U_0U_1}{U_{\rm pre}}(r_1-r_0)^2
\ge pq\frac{U_0\alpha^2}{U_{\rm pre}U_1}
\ge pq\frac{\alpha^2}{U_0}
\ge pq\alpha d_e.
\end{equation}
When $\alpha=0$, discard the nonnegative variance contribution.
The total converted variance is at most
\[
U_{\rm init}r_{\rm init}
=\PP(U,\ z\leftrightarrow B\mid\text{initial prefix})=d_f.
\]
The last equality is precisely the pivotal event for $f$ before its
bit is read. Using \eqref{eq:dfs-partition-pivots}, the converted variance therefore
bounds the conditional expected sum on the left of
\eqref{eq:dfs-future-pair-bound}. All contributions when $f$ is pivotal
occur inside the phase, as noted above, so this proves that estimate
with the sum over every later query.
Multiply \eqref{eq:dfs-future-pair-bound} by $pq d_f$, average over
the prefix of $f$, and sum over $f$. The sum of products over ordered
pivot pairs is bounded by
$\EE\sum_f pq d_f^2\le1$. Combining this with the diagonal bound
and the factor two for cross terms in $W^2$ proves $\EE W^2\le3$.
\end{proof}
\subsection{Entropy of overlapping transcripts}
For fixed coordinate subsets, related bounds are given by Shearer's
inequality \cite{ChungGrahamFranklShearer1986} and its relative-entropy
forms \cite[Section~IX]{MadimanTetali2010}. The read sets below are
adaptive, and their overlap is bounded only under a possibly dependent
comparison law.
We prove the required estimate by ordering the algorithms randomly
and charging each freshly queried bit to a common transcript.
A transcript records an algorithm's ordered queries and answers,
including its stopping decision. The next result charges several such
transcripts to the information in one common configuration. Its
overlap hypothesis is required only under the law being estimated.
For probability laws $Q,R$ on a finite set, let
\[
D(Q\Vert R)=\sum_x Q(x)\log\frac{Q(x)}{R(x)}
\]
be their relative entropy, with zero summands omitted.
\begin{lemma}\label{lem:entropy}
Let $\mu$ be the Bernoulli product law of parameter $0<p<1$ on
a finite set of bits, and let $Q$ be any probability law on those bits.
Consider finitely many terminating deterministic adaptive query algorithms, each
reading any bit at most once. Let $Q_i,\mu_i$ be their transcript
laws. Suppose that, on the support of $Q$, every bit is read by at
most $a$ algorithms, where $a\ge1$ is an integer. Then
\[
\sum_iD(Q_i\Vert\mu_i)
\le\frac{a^2}{2p(1-p)}D(Q\Vert\mu).
\]
\end{lemma}
\begin{proof}
Write $q=1-p$. At a pre-query node $h$ of algorithm $i$, let $e$
be the bit it queries and put
$b_h=\EE_Q[X_e-p\mid h]$. The transcript entropy chain rule and
the elementary Bernoulli bound
\[
d(r\Vert p):=r\log\frac rp+(1-r)\log\frac{1-r}q
\le\frac{(r-p)^2}{pq}
\]
give
\begin{equation}\label{eq:local-transcript-entropy}
\sum_iD(Q_i\Vert\mu_i)
\le\frac1{pq}\sum_{i,h}Q(h)b_h^2.
\end{equation}
The Bernoulli reference at each node is still $p$, since its own
history has not read that bit. The displayed bound follows from
$\log t\le t-1$, including endpoint values by continuity.
Assign independent uniform priorities in $[0,1]$ to the algorithms
and run them in priority order, caching previously read bits. Each
algorithm follows exactly its original path; a cached answer supplies
the same bit without a fresh query. For every fixed priority order,
the combined fresh-query transcript is a function of the configuration.
Data processing and the entropy chain rule give total fresh-query
entropy at most $D(Q\Vert\mu)$. The binary lower bound
$d(r\Vert p)\ge2(r-p)^2$ follows because its second derivative in
$r$ is $1/(r(1-r))\ge4$, and its value and first derivative vanish
at $r=p$. It implies
\begin{equation}\label{eq:global-transcript-budget}
\EE_{\rm priorities}
\sum_{g\text{ global fresh-query node}}Q(g)b_g^2
\le\tfrac12D(Q\Vert\mu),
\end{equation}
where $b_g$ is the conditional bias given the entire global pre-query
history and the fixed priorities.
Fix a local node $h$ of algorithm $i$ with $Q(h)>0$, querying $e$,
and condition its priority to be $t$. For a configuration $\omega$,
let $K_e(\omega)$ be the number of algorithms that read $e$.
On configurations visiting $h$, $1\le K_e\le a$, $Q$-almost surely.
The read paths are unchanged by caching. Conditional on such a
configuration, the query at $h$ is fresh exactly when all other
$K_e-1$ users have priority larger than $t$, an event of probability
$(1-t)^{K_e-1}$.
The number $K_e$ may be correlated with $X_e$ under $Q$, so this
freshness weight cannot be pulled out of a conditional expectation of
the bias. Retain their dependence by defining
\[
z_h(t)=\EE_Q[(X_e-p)(1-t)^{K_e-1}\mid h],\qquad
w_h(t)=\EE_Q[(1-t)^{K_e-1}\mid h].
\]
Pool the global pre-query nodes at which this local node is visited
fresh, averaging the other priorities. Their total probability is
$Q(h)w_h(t)$, and the sum of their probability-weighted biases is
$Q(h)z_h(t)$. This pooling is legitimate before the bit is read:
the current local node and membership in the cache are determined by
the global pre-query history. Cauchy--Schwarz thus bounds their
total squared-bias contribution below by
\begin{equation}\label{eq:entropy-pooled-bias}
Q(h)\frac{z_h(t)^2}{w_h(t)},
\end{equation}
with value zero when $w_h(t)=0$.
Every global fresh query belongs to exactly one local node, so these
lower bounds can be summed over all nodes.
At priority zero no other algorithm precedes $i$, so $z_h(0)=b_h$:
this endpoint recovers the original local bias. The overlap bound makes
$z_h$ a polynomial of degree at most $a-1$, since
$K_e\in\{1,\ldots,a\}$ on the conditional $Q$ support. Also
$0\le w_h\le1$. For any polynomial $z$ of degree
at most $a-1$, the classical shifted-Legendre endpoint bound
\cite[Tables~18.3.1 and~18.6.1]{DLMF} gives
\begin{equation}\label{eq:polynomial-endpoint}
|z(0)|^2\le a^2\int_0^1|z(t)|^2\,dt.
\end{equation}
Indeed, expand in the orthonormal shifted Legendre polynomials of
degrees $0,\ldots,a-1$. Their squared endpoint values are
$1,3,\ldots,2a-1$, with sum $a^2$, and Cauchy--Schwarz gives
\eqref{eq:polynomial-endpoint}.
Integrating \eqref{eq:entropy-pooled-bias} therefore yields at least
$Q(h)b_h^2/a^2$. Combine with
\eqref{eq:global-transcript-budget} and then
\eqref{eq:local-transcript-entropy} to prove the lemma.
No overlap bound under $\mu$ was used. The random variable $K_e$ may
be correlated with $X_e$ under $Q$; this correlation is retained inside
$z_h(t)$ throughout the argument.
\end{proof}
==== END No-percolation-at-criticality-on-quasi-transitive-graphs//two-cluster-dfs-entropy.tex ====
==== BEGIN No-percolation-at-criticality-on-quasi-transitive-graphs//references.bib ====
@article{BenjaminiSchramm1996,
author = {Benjamini, Itai and Schramm, Oded},
title = {Percolation beyond {$\mathbb Z^d$}, many questions and a few answers},
journal = {Electronic Communications in Probability},
volume = {1},
pages = {71--82},
year = {1996},
doi = {10.1214/ECP.v1-978},
url = {https://emis.de/ft/41630}
}
@article{Hutchcroft2016,
author = {Hutchcroft, Tom},
title = {Critical percolation on any quasi-transitive graph of exponential growth has no infinite clusters},
journal = {Comptes Rendus. Math\'ematique},
volume = {354},
number = {9},
pages = {944--947},
year = {2016},
doi = {10.1016/j.crma.2016.07.013},
eprint = {1605.05301},
archivePrefix = {arXiv},
url = {https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2016.07.013/}
}
@article{HermonHutchcroft2021,
author = {Hermon, Jonathan and Hutchcroft, Tom},
title = {No percolation at criticality on certain groups of intermediate growth},
journal = {International Mathematics Research Notices},
volume = {2021},
number = {22},
pages = {17433--17455},
year = {2021},
doi = {10.1093/imrn/rnz265},
eprint = {1809.11112},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/1809.11112v2}
}
@article{TesseraTointon2021,
author = {Tessera, Romain and Tointon, Matthew C. H.},
title = {A finitary structure theorem for vertex-transitive graphs of polynomial growth},
journal = {Combinatorica},
volume = {41},
pages = {263--298},
year = {2021},
doi = {10.1007/s00493-020-4295-6},
eprint = {1908.06044},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/1908.06044v3}
}
@misc{KozmaNitzan2024,
author = {Kozma, Gady and Nitzan, Shahaf},
title = {A reduction of the {$\theta(p_c)=0$} problem to a conjectured inequality},
year = {2024},
eprint = {2401.12397},
archivePrefix = {arXiv},
primaryClass = {math.PR},
doi = {10.48550/arXiv.2401.12397},
url = {https://arxiv.org/abs/2401.12397v1}
}
@misc{Leder2026,
author = {Leder, Justin},
title = {{$\theta(p_c)=0$} for {Bernoulli} bond percolation on {$\mathbb Z^d$} in all dimensions {$d\ge2$}: A guide to the {Lean} formalization},
year = {2026},
month = aug,
howpublished = {Public research announcement},
url = {https://github.com/anthropics/formal-math/blob/795efb86f191735c5481675763537cfb4ff37e55/percolation/summary.pdf}
}
@article{VanDenBergHaggstromKahn2006,
author = {van den Berg, J. and H{\"a}ggstr{\"o}m, O. and Kahn, J.},
title = {Some conditional correlation inequalities for percolation and related processes},
journal = {Random Structures \& Algorithms},
volume = {29},
pages = {417--435},
year = {2006},
doi = {10.1002/rsa.20102},
eprint = {math/0408176},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/math/0408176}
}
@article{Hutchcroft2020Locality,
author = {Hutchcroft, Tom},
title = {Locality of the critical probability for transitive graphs of exponential growth},
journal = {The Annals of Probability},
volume = {48},
number = {3},
pages = {1352--1371},
year = {2020},
doi = {10.1214/19-AOP1395},
eprint = {1808.08940},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/1808.08940v2}
}
@article{AizenmanKestenNewman1987,
author = {Aizenman, Michael and Kesten, Harry and Newman, Charles M.},
title = {Uniqueness of the infinite cluster and continuity of connectivity functions for short and long range percolation},
journal = {Communications in Mathematical Physics},
volume = {111},
number = {4},
pages = {505--531},
year = {1987},
doi = {10.1007/BF01219071},
url = {https://link.springer.com/article/10.1007/BF01219071}
}
@article{Harris1960,
author = {Harris, Theodore E.},
title = {A lower bound for the critical probability in a certain percolation process},
journal = {Proceedings of the Cambridge Philosophical Society},
volume = {56},
number = {1},
pages = {13--20},
year = {1960},
doi = {10.1017/S0305004100034241}
}
@article{Kesten1980,
author = {Kesten, Harry},
title = {The critical probability of bond percolation on the square lattice equals {$1/2$}},
journal = {Communications in Mathematical Physics},
volume = {74},
number = {1},
pages = {41--59},
year = {1980},
doi = {10.1007/BF01197577}
}
@article{HaraSlade1990,
author = {Hara, Takashi and Slade, Gordon},
title = {Mean-field critical behaviour for percolation in high dimensions},
journal = {Communications in Mathematical Physics},
volume = {128},
number = {2},
pages = {333--391},
year = {1990},
doi = {10.1007/BF02108785}
}
@article{FitznerHofstad2017,
author = {Fitzner, Robert and van der Hofstad, Remco},
title = {Mean-field behavior for nearest-neighbor percolation in {$d>10$}},
journal = {Electronic Journal of Probability},
volume = {22},
pages = {1--65},
note = {Paper No. 43},
year = {2017},
doi = {10.1214/17-EJP56},
eprint = {1506.07977},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/1506.07977}
}
@book{Robinson1996,
author = {Robinson, Derek J. S.},
title = {A Course in the Theory of Groups},
edition = {2},
series = {Graduate Texts in Mathematics},
volume = {80},
publisher = {Springer},
address = {New York},
year = {1996},
doi = {10.1007/978-1-4419-8594-1}
}
@article{VanDenBergKahn2001,
author = {van den Berg, J. and Kahn, J.},
title = {A correlation inequality for connection events in percolation},
journal = {The Annals of Probability},
volume = {29},
number = {1},
pages = {123--126},
year = {2001},
doi = {10.1214/aop/1008956324},
url = {https://doi.org/10.1214/aop/1008956324}
}
@article{Gromov1981,
author = {Gromov, Mikhael},
title = {Groups of polynomial growth and expanding maps},
journal = {Publications Math\'ematiques de l'IH\'ES},
volume = {53}, pages = {53--78}, year = {1981},
note = {With an appendix by Jacques Tits},
doi = {10.1007/BF02698687},
url = {https://www.numdam.org/item/PMIHES_1981__53__53_0/}
}
@article{Trofimov1985,
author = {Trofimov, V. I.},
title = {Graphs with polynomial growth},
journal = {Mathematics of the USSR-Sbornik},
volume = {51}, number = {2}, pages = {405--417}, year = {1985},
note = {English translation of Matematicheskii Sbornik 123(165) (1984), 407--421},
doi = {10.1070/SM1985v051n02ABEH002866},
url = {https://www.mathnet.ru/eng/sm2028}
}
@article{Trofimov2003,
author = {Trofimov, V. I.},
title = {Undirected and directed graphs with near polynomial growth},
journal = {Discussiones Mathematicae Graph Theory},
volume = {23}, number = {2}, pages = {383--391}, year = {2003},
doi = {10.7151/dmgt.1208},
url = {https://eudml.org/doc/270249}
}
@article{BreuillardGreenTao2012,
author = {Breuillard, Emmanuel and Green, Ben and Tao, Terence},
title = {The structure of approximate groups},
journal = {Publications Math\'ematiques de l'IH\'ES},
volume = {116}, pages = {115--221}, year = {2012},
doi = {10.1007/s10240-012-0043-9},
eprint = {1110.5008}, archivePrefix = {arXiv},
url = {https://arxiv.org/abs/1110.5008}
}
@article{GrimmettMarstrand1990,
author = {Grimmett, G. R. and Marstrand, J. M.},
title = {The supercritical phase of percolation is well behaved},
journal = {Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences},
volume = {430},
number = {1879},
pages = {439--457},
year = {1990},
doi = {10.1098/rspa.1990.0100},
url = {https://doi.org/10.1098/rspa.1990.0100}
}
@article{MartineauTassion2017,
author = {Martineau, S{\'e}bastien and Tassion, Vincent},
title = {Locality of percolation for {Abelian Cayley} graphs},
journal = {The Annals of Probability},
volume = {45},
number = {2},
pages = {1247--1277},
year = {2017},
doi = {10.1214/15-AOP1086},
eprint = {1312.1946},
archivePrefix = {arXiv},
url = {https://doi.org/10.1214/15-AOP1086}
}
@article{ContrerasMartineauTassion2023Locality,
author = {Contreras, Daniel and Martineau, S{\'e}bastien and Tassion, Vincent},
title = {Locality of percolation for graphs with polynomial growth},
journal = {Electronic Communications in Probability},
volume = {28},
number = {1},
pages = {1--9},
year = {2023},
doi = {10.1214/22-ECP508},
eprint = {2205.10253},
archivePrefix = {arXiv},
url = {https://doi.org/10.1214/22-ECP508}
}
@inproceedings{OSSS2005,
author = {O'Donnell, Ryan and Saks, Michael and Schramm, Oded and Servedio, Rocco A.},
title = {Every decision tree has an influential variable},
booktitle = {Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science},
year = {2005},
pages = {31--39},
publisher = {IEEE Computer Society},
doi = {10.1109/SFCS.2005.34}
}
@article{DuminilCopinRaoufiTassion2019,
author = {Duminil-Copin, Hugo and Raoufi, Aran and Tassion, Vincent},
title = {Sharp phase transition for the random-cluster and {Potts} models via decision trees},
journal = {Annals of Mathematics},
series = {2},
volume = {189},
number = {1},
year = {2019},
pages = {75--99},
doi = {10.4007/annals.2019.189.1.2}
}
@article{ChungGrahamFranklShearer1986,
author = {Chung, F. R. K. and Graham, R. L. and Frankl, P. and Shearer, J. B.},
title = {Some intersection theorems for ordered sets and graphs},
journal = {Journal of Combinatorial Theory, Series A},
volume = {43},
number = {1},
year = {1986},
pages = {23--37},
doi = {10.1016/0097-3165(86)90019-1}
}
@article{MadimanTetali2010,
author = {Madiman, Mokshay and Tetali, Prasad},
title = {Information inequalities for joint distributions, with interpretations and applications},
journal = {IEEE Transactions on Information Theory},
volume = {56},
number = {6},
year = {2010},
pages = {2699--2713},
doi = {10.1109/TIT.2010.2046253}
}
@misc{DLMF,
author = {{National Institute of Standards and Technology}},
title = {{NIST Digital Library of Mathematical Functions}},
year = {2026},
howpublished = {\url{https://dlmf.nist.gov/}},
note = {Version 1.2.8, released September 15, 2026; Tables 18.3.1 and 18.6.1; accessed September 24, 2026}
}
@article{BroadbentHammersley1957,
author={Broadbent, S. R. and Hammersley, J. M.},
title={Percolation processes. {I}. {Crystals} and mazes},
journal={Proceedings of the Cambridge Philosophical Society},
volume={53}, number={3}, pages={629--641}, year={1957},
doi={10.1017/S0305004100032680}
}
@article{AizenmanBarsky1987,
author={Aizenman, Michael and Barsky, David J.},
title={Sharpness of the phase transition in percolation models},
journal={Communications in Mathematical Physics},
volume={108}, number={3}, pages={489--526}, year={1987},
doi={10.1007/BF01212322}
}
@article{Menshikov1986,
author={Men'shikov, M. V.},
title={Coincidence of critical points in percolation problems},
journal={Doklady Akademii Nauk SSSR},
volume={288}, number={6}, pages={1308--1311}, year={1986},
note={English translation: Soviet Mathematics Doklady 33 (1986), 856--859},
url={https://www.mathnet.ru/eng/dan8543}
}
@article{BLPS1999Critical,
author = {Benjamini, Itai and Lyons, Russell and Peres, Yuval and Schramm, Oded},
title = {Critical percolation on any nonamenable group has no infinite clusters},
journal = {The Annals of Probability},
volume = {27},
number = {3},
pages = {1347--1356},
year = {1999},
doi = {10.1214/aop/1022677450}
}
@article{Timar2006Nonunimodular,
author = {Tim{\'a}r, {\'A}d{\'a}m},
title = {Percolation on nonunimodular transitive graphs},
journal = {The Annals of Probability},
volume = {34},
number = {6},
pages = {2344--2364},
year = {2006},
doi = {10.1214/009117906000000494},
eprint = {math/0702875},
archivePrefix = {arXiv},
primaryClass = {math.PR}
}
@article{DuminilCopinSidoraviciusTassion2016Slabs,
author={Duminil-Copin, Hugo and Sidoravicius, Vladas and Tassion, Vincent},
title={Absence of infinite cluster for critical {Bernoulli} percolation on slabs},
journal={Communications on Pure and Applied Mathematics},
volume={69}, number={7}, pages={1397--1411}, year={2016},
doi={10.1002/cpa.21641}, eprint={1401.7130}, archivePrefix={arXiv}
}
@misc{ConnectionInequalities2026,
author = {{ChatGPT 5.6 Sol} and {Claude Fable 5.1}},
title = {{Kozma--Nitzan} Connection Inequalities for {Bernoulli} Percolation},
year = {2026},
month = sep,
note = {Prompted by Ahmed Bou-Rabee; public manuscript, updated September 5, 2026},
url = {https://nitromannitol.github.io/kn1-verification-b80e9/document/kn_summary.pdf}
}
@misc{SiteCriticality2026,
author = {{ChatGPT 5.6}},
title = {Percolation at criticality},
year = {2026},
month = sep,
note = {With Claude Opus 5 and GLM 5.3 support; prompted by Ahmed Bou-Rabee. Public exposition and Lean development, September 5, 2026},
url = {https://nitromannitol.github.io/site-percolation-7d3f2/}
}
==== END No-percolation-at-criticality-on-quasi-transitive-graphs//references.bib ====