db38123
NONUNIQUENESS OF PERCOLATION ON NONAMENABLE QUASI-TRANSITIVE GRAPHS
==================================================================
A self-contained guided tour, written for curious high-school readers
who know a little probability (coins, dice, expected value) and a
little graph theory (vertices, edges, paths) and want to see how a
real research theorem is built. Everything needed is introduced
here.
This document is the accessible rewrite of "Nonuniqueness of
percolation on nonamenable quasi-transitive graphs". The original
technical paper is preserved next to this file; this rewrite keeps
the statements and the logical flow intact but replaces the dense
notation with plain language wherever possible, repairs a few typos,
and adds intuition that the research version assumes the reader
already has.
The two main results, in one sentence each:
1. Benjamini-Schramm. On any nonamenable quasi-transitive
graph, Bernoulli bond percolation has a genuinely nonempty
phase where the infinite open cluster fails to be unique.
2. Hutchcroft's operator threshold. The same class of graphs
satisfies p_c < p_{2->2} <= p_u, so the L^2 connection
operator is bounded at criticality.
The rest of this file explains what that means and why it is true.
. . . TABLE OF CONTENTS . . .
0. Prologue: what is percolation?
1. The two theorems, stated.
2. Graphs, thresholds, quasi-transitivity, amenability.
3. Basic probability tools used everywhere.
4. The overall strategy in one page.
5. Good clusters survive deletion.
6. Local endpoint maps (the amplification engine).
7. Critical moments of the cluster size.
8. The triangle trace stays subpower.
9. Corridors and deformation.
10. Finding paths with escapes at both ends.
11. The final contradiction.
12. Consequences and where to go next.
13. Glossary and index.
==================================================================
0. PROLOGUE: WHAT IS PERCOLATION?
==================================================================
Picture an enormous spiderweb: points (vertices) joined by silken
strands (edges). Now imagine that every strand is independent: with
probability p it is left intact ("open"), and with probability
1-p it is cut ("closed"). This is Bernoulli bond percolation.
The parameter p is a single number between 0 and 1: a dial that
runs from "everything cut" at p = 0 to "everything intact" at
p = 1.
A cluster is what you get by starting at some vertex and following
open strands as far as they will go. So the cluster of a vertex x
is the set of all vertices it can reach through open strands,
including x itself.
The big question: at which p does an infinite cluster appear?
When p is very small most strands are cut, so every cluster is a
tiny finitely sized puff. When p is very close to 1 almost every
strand is intact, and the whole network is one gigantic connected
blob. Somewhere in between, the cluster of any given vertex stops
being small and starts to be infinite with positive probability.
That special value of p is called the critical probability p_c.
On the ordinary infinite square grid (think graph paper going on
forever), a beautiful classical result says that at p_c there is
no infinite cluster, and just above p_c there is exactly one.
Everything is crisp — one threshold, one infinite cluster.
But on some graphs, there is a second threshold. Write
p_u for the smallest p such that there is almost surely exactly one
infinite cluster. On a regular tree of degree >= 3 (an ordinary
family tree extending forever upward), p_c and p_u are different.
There is a whole interval (p_c, p_u) in which there are infinitely
many infinite clusters simultaneously — a "many-infinite" phase.
For a long time it was conjectured (by Benjamini and Schramm in
1996) that this two-threshold behaviour is not special to trees or
to hyperbolic space: it happens on every "nonamenable" graph, which
is roughly a graph that expands faster than flat Euclidean space at
every scale. The first main result of this paper proves that
conjecture. The second strengthens it to the L^2 language
introduced by Hutchcroft: the boundary between "small" and
"large" is not just p_c and p_u but a third threshold p_{2->2}
that lives inside [p_c, p_u].
Percolation on nonamenable graphs is fascinating because the graph
itself is expanding: even if open strands are dense, they can get
"used up" fast enough that no single infinite cluster can dominate
the whole graph. The intuition — that nonamenability forces
nonuniqueness — was already known in special cases. This paper
proves it in complete generality for bond percolation on any
nonamenable graph with finitely many symmetry classes of vertices.
==================================================================
1. THE TWO THEOREMS, STATED
==================================================================
Before stating anything, we need a small dictionary. We write
G the infinite connected graph
V, E its vertices and edges
x ~ y "x is joined to y by an edge"
Aut(G) the group of graph automorphisms
(bijections of V preserving edges)
quasi-transitive Aut(G) has only finitely many orbits on V
h_V(G) the vertex isoperimetric constant of G (below)
p_c(G) the critical probability
p_u(G) the uniqueness threshold
T_p(x,y) Prob_p (x is connected to y by an open path)
p_{2->2}(G) the L^2 operator threshold (below)
Isoperimetric constant. For a finite set A of vertices, the vertex
boundary of A is the set of vertices outside A that are adjacent to
some vertex of A:
dA = {v not in A : v ~ a for some a in A}.
Then
h_V(G) = inf_A |dA| / |A|,
where the infimum runs over all finite nonempty A. The graph is
amenable if h_V(G) = 0 and nonamenable if h_V(G) > 0.
What nonamenability means in words: every finite lump of vertices
has a boundary of at least a fixed fraction of its own size. In a
flat grid, lumps of radius R have size about R^2 and boundary about
R, so the ratio shrinks to 0: the grid is amenable. In a tree of
degree d >= 3, lumps of radius R have size about d^R and boundary
about d^R: the ratio is bounded below. A tree is nonamenable.
Thresholds. Define, with N_inf(p) = number of infinite open
clusters (a random variable taking values in {0, 1, 2, ..., inf}):
p_c = inf { p : Prob_p (N_inf(p) >= 1) > 0 }
p_u = inf { p : Prob_p (N_inf(p) = 1) = 1 }.
By monotonicity (opening more strands can only help), these are
well-defined numbers in [0, 1], and 0 <= p_c <= p_u <= 1.
The connection operator. For each p, T_p is the infinite matrix
T_p(x, y) = Prob_p (x <-> y). Because T_p >= 0 (all entries are
nonnegative probabilities), T_p has a natural action on functions
with compact support via
(T_p f)(x) = sum_y T_p(x, y) f(y).
This acting-on-functions language is the language of Hilbert space
L^2(V): square-summable functions with inner product
<f, g> = sum_x conj(f(x)) g(x).
We say T_p is bounded on L^2(V) if there is a finite constant M
such that ||T_p f||_2 <= M ||f||_2 for every finitely supported f.
That constant is the operator norm ||T_p||_{2 -> 2}.
The operator threshold p_{2->2} is the supremum of p for which
T_p is bounded. It always satisfies p_c <= p_{2->2} <= p_u.
The non-trivial content of the second theorem is that the
inequalities are strict at the left.
Now the theorems.
THEOREM (Benjamini-Schramm). Let G be an infinite connected
locally finite quasi-transitive graph. If G is nonamenable, then
p_c(G) < p_u(G).
THEOREM (Hutchcroft's operator threshold). With G as above, the
L^2 norm ||T_p||_{2 -> 2} is continuous at p_c from below, and
sup_{p < p_c} ||T_p||_{2 -> 2} = ||T_{p_c}||_{2 -> 2} < infinity.
In particular,
p_c(G) < p_{2->2}(G) <= p_u(G).
Also, there exist p_c < p_1 < p_2 < 1 and a single coupling (all
graphs drawn from independent uniform edge labels) such that
almost surely, for every p in [p_1, p_2], there are infinitely many
infinite open clusters.
Read the second theorem carefully: at p_c itself the connection
kernel is a bounded operator, even though its rows can be infinite.
The "at p_c from below" clause says criticality is not a point of
sudden blow-up; it is already "visible" as a bounded limit from
below. The two-threshold gap p_c < p_{2->2} is what makes the
corridor argument in the proof work.
Consequence for any Cayley graph. Let Gamma be a nonamenable
finitely generated group, and let S be any finite symmetric
generating set (not containing the identity). The Cayley graph has
vertices Gamma and edges {x, xs} for x in Gamma and s in S.
Corollary: it satisfies p_c < p_{2->2} <= p_u, for every such S.
No choice of generators is needed, unlike earlier results.
==================================================================
2. GRAPHS, THRESHOLDS, QUASI-TRANSITIVITY, AMENABILITY
==================================================================
This section is the working dictionary for everything that follows.
Read it once, then dip into it as needed.
2.1 Graphs.
A graph G = (V, E) has a vertex set V and an edge set E, where
each edge is an unordered pair {x, y} of distinct vertices. The
degree deg(x) is the number of edges incident to x. The graph is
locally finite if every degree is finite, and bounded-degree if
sup_x deg(x) < infinity. It is connected if every two vertices
are joined by a path. In this paper we additionally require V to
be countably infinite and connected.
For a vertex set A, the induced subgraph G[A] keeps all vertices
in A and all edges whose two endpoints lie in A. We often write
just A for G[A].
2.2 Orbits and quasi-transitivity.
An automorphism of G is a bijection phi: V -> V with x ~ y
if and only if phi(x) ~ phi(y). The group Aut(G) acts on V.
The orbit of a vertex x is
O_x = { phi(x) : phi in Aut(G) }.
The graph is transitive if there is one orbit; quasi-transitive if
there are finitely many. In words: quasi-transitive graphs have a
bounded pattern book — a finite list of vertex types and a rule
that any type can be moved to any other copy of the same type by a
symmetry.
Quasi-transitivity has consequences. Vertex degrees are uniformly
bounded. Every vertex is within a bounded distance of every vertex
orbit. We can count "how many" of each type appear by giving each
type a positive weight, and using those weights to average over
types. This "type average" is the discrete analogue of averaging
over the whole graph in the transitive case.
2.3 Percolation and thresholds.
Bernoulli bond percolation at parameter p: to each edge of E,
independently assign "open" with probability p and "closed" with
probability 1-p. The randomly chosen graph of open edges is denoted
G_p. The open cluster of x is the connected component of x in G_p,
denoted C_x. Its size is s_x = |C_x| in N union {infinity}.
The events {x <-> y} (there is an open path from x to y) are
increasing: opening more edges can only help. The probabilities
T_p(x, y) are nondecreasing in p.
The two thresholds p_c and p_u are as written above.
On any infinite connected graph, 0 < p_c < 1. The lower inequality
is by counting paths (there are at most d^n length-n paths, and
that is too few to reach infinity when p is tiny). The upper is by
counting missing edges (in a bounded-degree graph, very few short
balls fail to be entirely open once p is close to 1).
If the graph is nonamenable, then p_c < 1 is a strict consequence
of the existence of an exponential-growth argument; in particular,
critical percolation has no infinite cluster (a theorem due to
Benjamini-Lyons-Peres-Schramm for Cayley graphs and to Hutchcroft
for arbitrary quasi-transitive graphs of exponential growth).
2.4 Amenability in more detail.
The isoperimetric constant h_V(G) appears in the definition of
nonamenability. Let us see it in two examples.
Square grid Z^2.
Ball of radius R: |B_R| = (2R+1)^2, |dB_R| = 4R + 4.
Ratio: (4R+4)/(2R+1)^2 -> 0. Amenable.
Regular tree of degree d >= 3.
Ball of radius R: |B_R| ~ d * (d-1)^{R-1}.
Boundary: (d-1)^R.
Ratio: (d-1)^R / (d (d-1)^{R-1}) = (d-1)/d > 0. Nonamenable.
Nonamenable quasi-transitive graphs are exactly those that grow
exponentially and have a spectral gap for the simple random walk on
them: the lazy walk's L^2 operator P has norm rho < 1. That
spectral gap is exploited constantly in the proof.
2.5 The lazy random walk.
Define a Markov chain P on V by
P(x, y) = 1/(2d) if x ~ y,
P(x, x) = 1 - deg(x)/(2d),
P(x, y) = 0 otherwise,
where d is a uniform upper bound on degrees, and (x, y) with
y = x is the "staying put" probability. Two important facts, both
proved in the paper:
P is a symmetric stochastic kernel,
P is positive semidefinite on L^2(V),
||P||_{2->2} = rho < 1 (because G is nonamenable).
The walk kernel P is used everywhere: as a way to smooth mass, as a
source of independent random templates, and as the mechanism that
gives the "random escape" in the corridor argument.
2.6 Two important operator facts.
We will repeatedly use:
(a) Doeblin-type domination. If |A(x, y)| <= B(x, y) entrywise
and B is a nonnegative bounded kernel, then ||A|| <= ||B||.
(Proved by testing against |f| and |g|.)
(b) Row/column bound. If every row sum and every column sum of a
nonnegative kernel B is at most beta, then ||B|| <= beta.
(Cauchy-Schwarz on the bilinear form.)
Both are elementary, but they are the bread and butter of every
operator estimate in the paper.
==================================================================
3. BASIC PROBABILITY TOOLS USED EVERYWHERE
==================================================================
Three inequalities handle almost every probabilistic estimate in the
proof. We state and explain them, with the "why" first and the
statement second. The proofs are short and included.
3.1 Harris's inequality (positive association).
Intuition. If you take two "monotone increasing" events about a
random system — events that only become more likely when more edges
open — they can only help each other. There is no anti-dependence.
Formal statement. Let X = (X_i) be a finite product measure (here:
the open/closed bits of the edges). If f and g are both increasing
functions of X (open an edge => f cannot decrease), and both are
nonnegative, then
E[f(X) g(X)] >= E[f(X)] E[g(X)].
Equivalently, Cov(f, g) >= 0.
The same statement extends to the infinite-product setting by
truncation: restrict to a finite edge set, apply the finite result,
and let the finite set grow.
Proof idea. Condition on the last coordinate. The conditional
expectations E[f | last], E[g | last] are both increasing in the last
coordinate (because opening that edge cannot hurt either event).
For two increasing functions of one bit, the covariance is
nonnegative. Induct on the number of bits.
This is where the name "Harris" comes from (Harris 1960). In
statistical physics it is also called the FKG inequality.
3.2 The van den Berg-Kesten (BK) inequality.
Intuition. Suppose event A needs a certain open "witness set" W_A of
edges, and event B needs its own witness set W_B. If the two
witnesses could be taken disjoint, the joint probability is at most
the product of the marginal probabilities. Disjoint witnesses make
the two events "effectively independent" from the point of view of
opening edges.
Formal statement. If A is increasing and has finite minimal open
witnesses, and B likewise, define the "disjoint occurrence"
A [] B = "there exist disjoint witnesses W_A for A and W_B for B".
Then
Prob(A [] B) <= Prob(A) Prob(B).
For independent percolation on a graph, the classic application is:
if A and B need open paths through disjoint edge sets, then their
joint probability is at most the product.
Proof idea (finite product). Induct on the number of edges. Split
the last bit into section 0 (up to scaling) and section 1. The
"0-section" and "1-section" of A [] B sit inside the corresponding
sections of the smaller problem; induction plus a short algebraic
check gives the result. For p > 1/2, replace each open bit of
parameter p by the OR of m independent bits of parameter
q = 1 - (1-p)^{1/m}; for m large q is below 1/2, and a disjoint
witness for the enlarged system projects to a disjoint witness for
the original. This trick handles all p in (0, 1).
BK is exactly the reason the "triangle" appearing later is such a
powerful diagnostic of connectivity structure: the probability that
two long paths share extra edges becomes a product.
3.3 The three-arm estimate.
The most-used BK consequence is the following. For any x, y, z:
Prob_p (x <-> y and x <-> z)
<= sum_w T_p(x, w) T_p(w, y) T_p(w, z).
Why. On the joint event, there is a finite open tree joining x, y,
z. Its branch vertex w has three edge-disjoint paths from w to the
three terminals (a path of length 0 is allowed). Union over w,
then BK.
The sum on the right is the so-called triangle diagram: the matrix
product T_p * T_p * T_p evaluated at (x, z), but summed over w.
This is where the phrase "triangle condition" comes from.
3.4 Sprinkling.
Idea. If you take a graph with edges open at parameter p and then
"add" a second independent batch of open edges at parameter a, the
result is a graph with edges open at parameter p + (1-p) a. This
process of adding an extra batch is called sprinkling. Rather than
"increasing p to p + delta", we can think of it as: existing open
edges stay; a fraction a of the previously closed edges also open.
Formal statement. For 0 <= p, a <= 1,
T_{p + (1-p)a}(x, y)
<= sum_{j >= 0} a^j [T_p (Adj T_p)^j](x, y).
The right side is the sum over all "extra-open" edges of the
sprinkled graph of the probability that the base path uses exactly
j of them. Because BK gives products across the base-field segments,
each term contributes a^j times the correct product of connection
probabilities, and the sum over intermediate vertices only helps
(the right side is an upper bound, not an exact value).
Consequence. If ||T_p|| is bounded and a d ||T_p|| < 1 (where d is
the max degree), then the sprinkled kernel is also bounded. In
particular, if T_p is bounded, then so is T_{p + delta} for small
delta > 0. That is how "boundedness at p_c" pushes boundedness
just above p_c, giving p_c < p_{2->2}.
3.5 The two "operator facts" from 2.6, in practice.
We state them again together with their typical use.
Doeblin domination. If 0 <= A <= B entrywise and B is a nonnegative
bounded kernel, then ||A||_{2->2} <= ||B||_{2->2}. Application: to
bound any operator, find a dominating nonnegative kernel whose norm
we already control.
Row/column bound. If a nonnegative kernel B has all row sums and all
column sums at most beta, then ||B||_{2->2} <= beta. Application:
stochastic matrices are automatically contractions; stochastic
matrices with column sums one also are, and this lets us move masses
around freely without changing norms.
These two are the routine which every estimate in this paper is
eventually fed through.
==================================================================
4. THE OVERALL STRATEGY IN ONE PAGE
==================================================================
We prove that ||T_{p_c}||_{2 -> 2} is finite. From that and
sprinkling we get p_c < p_{2->2}, and from that plus the fact that
uniqueness forces an unbounded T_p we get p_{2->2} <= p_u.
So the whole task is: bound ||T_{p_c}||.
Direct lower bound on ||T_{p_c}||. Ask: is there a finite constant
M such that ||T_p|| <= M for all p < p_c? Equivalently by the
monotone limit lemma (which we prove later), ||T_{p_c}|| <= M.
The row sum of T_p at x is the expected size chi_x(p) = E_p |C_x|.
If we could bound chi uniformly we would be done. We cannot, in
general: chi_x(p) -> infinity as p -> p_c.
So we need a different mechanism. The operator norm ||T_p|| is
at most sup_x chi_x(p), but it can be strictly less — even tend to
infinity much more slowly than chi does, or be bounded while chi
blows up. The hard content of the theorem is that on nonamenable
graphs this "cheaper than chi" behaviour holds at p_c: the operator
stays bounded even while its row sums diverge.
The proof has five moving parts. Each one is a barrier.
Part A: Fractional moments of the cluster size.
Assume for contradiction that chi_x(p_c) blows up so fast that
even a fractional moment E_{p_c} s_x^alpha, for some
alpha in (0, 1/2), is infinite. Once confirmed, we are going
to derive a contradiction from it. If no such alpha exists,
the theorem is already on its way to being true.
Part B: Small endpoint maps with enormous dispersion.
Under the fractional-moment blowup, we build a randomized rule
which either fails, or picks out a vertex in the root's cluster
with properties that scale "wrong". The rule's success
probability u is not too small, but its conditional endpoint
kernel K has tiny norm r. In words: the rule spreads endpoints
very widely while remaining likely to succeed. Making r the
small parameter in the proof is the key.
Part C: The map as an operator.
Each map is a subcritical object (it is built from a scale that
sits inside the root cluster and can be run at any p < p_c).
Its small norm is what makes it destructive as an operator.
Part D: A differential inequality.
Iterate the map. Its tiny norm pushes mass outside the root
cluster; exposing the cluster and applying the map on the
exterior gives a fine upper bound on how much of the resulting
mass lands inside the original cluster. Comparing to a
full-graph susceptibility gives a lower bound for "how
exterior" the iterates must be. Interpolating the two forces
a strong lower bound on chi'(p), which is the key estimate.
Part E: The corridor deformation.
Even a subpower bound on chi and on the "triangle trace"
(essentially the third moment of T_p) is not enough on its own
because a nonamenable graph can still push up the operator norm
through sheer visual density. We therefore add a penalty to
connections that use a "corridor" — a simple open path with no
side opening at its interior. Applying the penalty strictly
reduces the row sums, while only mildly reducing the operator
norm, thanks to the spectral gap of the lazy walk.
Combining D and E forces a contradiction, proving that
||T_{p_c}|| < infinity. Then:
boundedness at p_c + sprinkling => p_c < p_{2->2}
p_{2->2} <= p_u (proved directly)
strict gap + coupling argument => simultaneous interval
Each of the following sections corresponds to one of the moving
parts. They are all long; read each as an independent story, not
as a linear script.
A note on quantifier order. The proof fixes all "path constants"
in advance (they depend only on the graph), then closes the
subcritical parameter p to p_c and then deforms. This is why the
statement "there exists a K_* depending only on G" appears so often:
constants must be independent of p and of any auxiliary objects.
==================================================================
5. GOOD CLUSTERS SURVIVE DELETION
==================================================================
5.1 What is this for.
When we later "cut" a piece out of an open cluster and paste it somewhere
else, we need to know that the piece is well-behaved no matter how it
was cut. Precisely, we need: after removing an arbitrary set of
vertices from an original cluster, each surviving connected piece keeps
track of its bridge structure. The number of bridges inside any such
piece is controlled by the number of open edges that originally
attached the piece to the deleted region.
That is a property of "generic" critical clusters. It fails only on a
stretched-exponentially small set of cluster shapes. The whole
section is here to prove this.
5.2 Pivotal bridges and pivotal distance.
In an open connected graph H (think: a cluster, or a piece of one),
a bridge is an open edge whose deletion disconnects H.
Given two vertices in H, the pivotal distance between them is the
number of bridges separating them. Equivalently: delete every
bridge, contract the resulting connected pieces (2-edge-connected
components), and measure graph distance in the resulting tree.
Call the tree the pivotal tree of H.
We write diam_piv(H) for the maximum pivotal distance between any two
vertices, and rad_piv(H, x) for the maximum pivotal distance from a
fixed vertex x.
5.3 Good clusters.
Fix epsilon in (0, 1/2) and set s = 1/2 + epsilon. We say a finite
open cluster C with |C| <= M is good for cap M if:
For every subset A of C, for every open component B of C minus A,
with K_B = number of original open edges from B to A (>= 1 in
every nontrivial piece), we have
diam_piv(B) <= K_B * M^s,
where pivotal distance is measured inside B.
In words: after "cutting" the cluster C along an arbitrary set A, each
surviving piece has pivotal diameter at most (its number of re-attachments
to A) times M^s. Since M^s grows only like the square root of M (for
fixed epsilon), this is a strong constraint on the piece's bridge
structure.
5.4 The proposition.
Proposition 5.1 (Good critical clusters). Fix epsilon in (0, 1/2).
There is a M_0 such that for all M >= M_0 and every vertex x,
P_{p_c}( s_x <= M and C_x is not good for cap M ) <= exp(-M^epsilon).
The event {s_x <= M and C_x good for cap M} depends on the percolation
inside a deterministic finite-radius ball around x. (This "locality"
is used later when we compare two different percolation fields.)
The rest of the section is the proof.
5.5 The ghost marks.
Let h in (0, 1/2] be a small parameter. Independently of the percolation
field, mark each vertex with probability h. This is called a "ghost
field" or "mark field" because the marked vertices act as witnesses.
Fix an induced domain D containing x. Let E be the event that C_x^D
contains at least one marked vertex.
Consider an edge. It is pivotal for E if toggling its state changes
whether the event E holds. Let D_p denote the number of open
pivotal edges of E. (The subscript p reminds us we are at percolation
parameter p = p_c.)
Two facts about the pair (E, D_p) drive everything:
Fact (5.5.a). Every pivotal edge is a bridge in C_x^D. Moreover,
along each bridge from x to a marked vertex, the pivotals are
linearly ordered.
Fact (5.5.b). If a marked vertex is at pivotal distance r from x,
then the number of pivotals on the path from x to that mark is
at least r.
These pin the connection between the mark event and the pivotal count.
5.6 Concentrating the count.
Let T be the number of edge bits explored by a fixed mark-detecting
algorithm that stops either when it discovers a marked vertex, or when
the cluster is exhausted. Because we choose a mark-independent query
order, no edge is queried twice.
Lemma 5.2 (First moment of D_p). There is a constant A_h, depending
only on d and p_c, such that for every induced domain D, every x in D,
and every r >= 0:
E[ D_p * 1_E ] <= A_h * P(E),
P( E and D_p >= r ) <= 2 P(E) * exp( -r / (4 A_h) ),
with
A_h = C * sqrt( log(1/h) / h ),
for a constant C depending only on d and p_c.
So the number of pivotals is exponentially concentrated above its mean,
and the mean is bounded by A_h. The point of the sqrt(log(1/h)/h)
is that it stays bounded as h -> 0 (slowly): we can afford to use
ghost marks with tiny h.
Proof outline.
(i) Bound E[T | E] <= d/h. A cluster of length s has at most ds
incident edges, and conditioning on E to be the first mark
makes E[s | E] <= 1/h by a geometric-tail argument.
(ii) Score identity. Let
Z = sum_{e queried} (omega_e - p_c),
with omega_e = 1 if e is open. Let Q_e be the indicator that e
was queried. Q_e is independent of omega_e. Then
E[ Z * 1_E ] = (1 - p_c) E[ D_p * 1_E ].
The intuition: only pivotal edges make a nonzero contribution
to Z on E, and each open pivotal edge contributes a factor
p_c (1 - p_c) after averaging.
(iii) Exponential moment of Z. Each queried bit is fresh. For a
centered Bernoulli variable, the log-moment-generating
function is at most lambda^2 / 8. Successive conditioning
gives
E exp( lambda Z - lambda^2 T/8 ) <= 1.
Conditional Jensen's inequality with H = P(E) >= h,
yields
lambda E[Z | E] <= log(1/H) + (lambda^2 / 8) E[T | E].
Choosing lambda = sqrt( 8h log(1/h) / d ) and plugging back
gives the first-moment claim.
(iv) Higher binomial moments. Let b_i(D, x) = E[ binom(D_p, i) 1_E ]
for i >= 1. Decompose the i-th binomial moment according to
its first selected pivotal, oriented away from x. This gives
the recursion
b_i(D, x) = p_c * sum_{oriented e = (a, b) in E(D)}
sum_{W: x, a in W, b not in W}
P( C_{x,e}^D = W )
(1 - h)^{|W|}
b_{i-1}( D \ W, b ),
where C_{x, e}^D is the root cluster after forcing e closed.
The recursion shows b_i <= A_h^{i-1} b_1 <= A_h^i P(E) by
induction. Then an insertion of (1 + 1/(2A_h))^{D_p}
and Markov's inequality produces the exponential tail.
The upshot: E and D_p are exponentially controlled.
5.7 From pivotals to the pivotal radius.
Lemma 5.3 (Capped pivotal-radius tail). For the fixed epsilon in
(0, 1/2), there is a constant c > 0 such that, uniformly in x, in
all sufficiently large M, and in all integers 1 <= K <= M^{1-s},
P( s_x <= M and rad_piv(C_x, x) >= K M^s / 2 )
<= exp( -c K^2 M^{2 eps} / log M ).
Sketch. On the bad event, choose a witness vertex y at pivotal
distance at least K M^s / 2. Independently mark vertices with
probability h. On the event that y is the unique mark in C_x,
every bridge separating x from y is pivotal for E, so D_p >= K M^s / 2.
Then by Lemma 5.2:
P( s_x <= M, rad_piv(C_x, x) >= K M^s / 2 )
<= (1 / (h (1-h)^M)) * exp( -K M^s / (8 A_h) ).
Setting h = K^2 M^{-1+2eps} / (b log M) for a large constant b makes
the exponent dominate log M, and combining with (1-h)^{-M} <=
exp(2h M) finishes.
The constant c is not optimized; what matters is the shape: the
probability is stretched-exponentially small as M -> infinity, and
the exponent is quadratic in K.
5.8 From capped pivotal tail to the goodness proposition.
Suppose now that C_x is capped at size <= M but not good for cap M.
By definition there is a set A and a surviving component B
witnessing the violation: |dB-exchange| = K, and diam_piv(B) > K M^s.
Modify the configuration by closing all but one (if x is not in B)
of the open edges from B to A. The modified root cluster C'_x still
contains B, and B is now attached to the rest of C'_x by exactly one
edge (or zero edges if x is in B). Inside C'_x, the bridges of B
cannot have extra parallel connections, so they are also bridges of
C'_x. Hence C'_x has pivotal radius at least K M^s / 2 from x.
Since the modified configuration is at most "K edge flips" away from
a configuration in the event of Lemma 5.3, we can compare the
probabilities. For fixed K, the modification is a finite-product
comparison:
number of possible inputs <= (K + 1) (dM)^K,
probability ratio input/output <= max(1, p_c/(1-p_c))^K.
Combining with Lemma 5.3 gives, for the contribution of fixed K,
<= exp( C_1 K log M - c K^2 M^{2 eps} / log M ).
Then summing over K in [1, M] gives, since M^{2 eps} / (log M)^2 -> inf,
P( s_x <= M, C_x not good ) <= M exp( -c M^{2 eps} / (2 log M) )
<= exp( -M^eps ) for large M.
The locality statement: to test whether C_x is good for cap M with
|C_x| <= M, we only need to know the internal edges of C_x and its
closed boundary, all of which are inside the ball of radius M around x.
==================================================================
6. LOCAL ENDPOINT MAPS (THE AMPLIFICATION ENGINE)
==================================================================
6.1 The hypothesis we work under.
For a little while we assume for contradiction:
there exists alpha in (0, 1/2) such that, at p_c,
E_{p_c} s_x^alpha = infinity (6.1)
for every (or at least one) x. This is the "Part A" of the strategy.
If no such alpha exists, the argument breaks off and the theorem is
true; so we are allowed to reason as if (6.1) holds.
Pick beta > alpha and epsilon > 0 with beta + s < 1, where s = 1/2 +
epsilon (same epsilon as Section 5). All our constructions are going
to depend on these choices.
Lemma 6.1 (Selection of an orbit and of scales). Given (6.1), there
is a vertex orbit O, a positive constant c > 0, and a sequence N of
dyadic integers n going to infinity, such that for every n in N:
(a) pi_n := P_{p_c}(n <= s_o < 2n) >= n^{-beta};
(b) P_{p_c}(n/2 <= s_o < 2n) <= (1 + 2^beta) pi_n;
(c) for every x in O,
E_{p_c}[ |C_x cap O| * 1_{n <= s_x < 2n} ] >= c n pi_n.
The same orbit and sequence work for all our later construction.
Proof sketch. Sum E s_o^alpha over dyadic shells [2^j, 2^{j+1}).
If pi_j = P(2^j <= s_o < 2^{j+1}) were eventually of size less than
2^{-beta j}, the sum would converge; the hypothesis (6.1) says it does
not, so pi_j must be at least 2^{-beta j} along infinitely many j.
Take those j as N. Part (c) comes from applying transport to a
"good" subset of each cluster (the vertices whose orbit fills at
least a fixed positive fraction of that cluster) and a pigeonhole
argument over the finitely many vertex orbits. See the paper for the
full details.
The point of (6.1)-(c): we can find scales at which a heavy tail is
being realised simultaneously by a nontrivial chunk of a single vertex
orbit. These are the scales at which we do a "splice".
6.2 Local endpoint maps.
A local endpoint map on O is a random rule that, at each x in O,
looks at the percolation field in a fixed finite ball around x (plus
its own independent randomization), and either fails or outputs a
vertex y in C_x cap O. It has a cap M if on every successful input:
the whole cluster C_x has size <= M, and
C_x is good for cap M (definition in Section 5).
"Local" means the rule only reads finitely many bits; "covariant"
means the rule commutes with automorphisms of the graph (so it is
consistent on all of O).
For such a map, define the following numbers:
u = success probability (of the map at p_c);
K(x, y) = conditional probability of output y given success at x;
r = || K ||_{2->2} (the operator norm of K on l^2(O));
M = cluster-size cap;
U = log(1/u);
m = log M;
H = log(1/r).
K is a stochastic kernel (rows sum to one). By transport, K also has
column sums equal to one, so 0 < r <= 1. Large U: the map usually
fails. Large m: big clusters allowed. Large H: endpoints are very
spread out.
The "figure of merit" for a useful map is
(U + m) / H.
If this is small, the map spends relatively little in log-probability
on failures and caps, and gains a lot in dispersion. That is what
makes it destructive as an operator.
Proposition 6.3 (Efficient endpoint maps). Under (6.1), for every
eta > 0 there is a local endpoint map with M >= 2 and H > 1 such
that
(U + m) / H < eta,
and moreover the maps can be chosen with H -> infinity. Their radii
are finite, but bounded only by constraints we choose in the
construction.
The rest of the section proves this proposition in four steps:
a starting map; an amplification step; a second-moment estimate; and
iteration.
6.3 The starting map.
The starting map is a walk-based rule.
Lemma 6.4 (Starting map). There is a local endpoint map on O with
H > 1 and with arbitrarily large cap.
Construction. Fix a walk length ell. Given x in O, run a random
walk of length ell with transition kernel P (the lazy walk from
Section 2). Require:
- the endpoint of the walk lies in O;
- every distinct edge traversed by the walk is open.
If the walk takes e distinct traversals, accept the result with
probability p_c^{ell - e} (a "hold" coin per repeated step). This
makes the unconditional endpoint kernel at x exactly p_c^ell P^ell
restricted to O x O. Then cap-reject and goodness-reject, i.e. rule
out any success where C_x has size > M or is not good for cap M.
Why this works.
Row sum: Since the type chain mixes, for large ell the walk's
row sum to O is at least c_1 p_c^ell for a fixed c_1 > 0.
Norm: The operator norm of p_c^ell P^ell is at most p_c^ell
rho^ell (because ||P|| = rho). Pick ell such that
2 rho^ell / c_1 < e^{-1}. Then the norm of the un-cap-rejected
map is < e^{-1} = r.
Cap-rejection: Since percolation at p_c is finite (Section 2)
and P_c(s_x <= M) -> 1 as M -> infinity, choose M large enough
that the cap-rejection loses at most half of the row sum.
Same for goodness (Proposition 5.1).
Result: a local endpoint map with h = log(1/r) > 1 and any prescribed
cap M.
6.4 Splicing: the switching construction.
Given an old map with parameters (u, M, r), an integer k >= 1, and a
scale n in N with k M <= n/2, we build a new, better map. This is
where the "amplification" happens.
Intuition. Imagine the old map as: "pick a small cluster in front of
you, then walk towards a target using the map". Now run k such steps
in a row, chained together. If each step succeeds, we have a chain
of k small clusters connecting two far-apart vertices. The chain
propagates the endpoint of the old map to a much farther point — the
endpoint of the chain — with probability (roughly) u^k, but the norm
of the new endpoint kernel is (roughly) r^k, which is far smaller
because r < 1 and k grows. That is the amplification.
Construction.
Fix x in O. Start with a "background" distinguished field D in
which we require
A = C_x(D) has n <= |A| < 2n. (6.2)
Independently, start from any other vertex z in O and take k
old-map steps, each using its own fresh percolation field and fresh
seeds. We ask: does the last endpoint land in A?
The experiment has mass 1/n if all k steps succeed and the last
endpoint is in A, and mass zero otherwise. (The 1/n weights the
initial bin of scales.)
A successful chain, listed backwards, is:
y_0 in A, y_1, ..., y_k = z.
Each C_i (i = 1, ..., k) is the whole cluster in the field E_i used
between y_i and y_{i-1}; each C_i is good for cap M and has
at most M vertices.
Switching procedure. Now we want to "splice" the chain into the
background field D, so that the root cluster of x in the modified D
contains all the pieces. The idea: move open edges one at a time.
Start with S = A. Repeat the following until z in S:
(i) Choose the largest index i with C_i meeting S (and i not
yet used).
(ii) Let B_i be the component of y_i in the open subgraph of
E_i induced by V minus S.
(iii) Among the K_i open E_i-edges from B_i to S, choose one
edge e_i uniformly at random.
(iv) Exchange the D- and E_i- open/closed bits on the "mask"
{ e_i } union
{ e : e is incident to B_i and both endpoints outside S }.
After the exchange, the root cluster grows from S to S union B_i.
Key property (Lemma 6.5, the geometry).
Every step of the procedure is well defined.
Its effect on the distinguished root cluster is exactly
S --> S union B_i.
The seams e_i at each step are the only open contacts between the
piece B_i and the rest of the root cluster.
Each seam separates x from z in the final field D'.
The final root cluster C_x(D') satisfies
z in C_x(D'), and s_x(D') <= M' := 2n + k M.
Why the seams are bridges. At every step, the D-field is such that
all edges from S to outside S are closed. When we exchange the E_i
bits into D on the mask, the new S contains B_i with e_i its sole
open edge to the prior S. Every other edge to S stays closed. Edges
internal to S are unchanged. So the joints are bridges.
Why later pieces attach to their immediate predecessors and not to
earlier ones. Whenever we select i, no higher index was eligible
at the previous step; that means C_j misses the prior (smaller) S
for all j > i. So the enlarged S = S union B_i is only reachable
from the remaining chain through B_i. Inductively, each inserted
piece attaches only to its immediate predecessor, and the seams
form a chain.
6.5 Coding the inverse.
To bound the mass of valid outputs, we reverse the whole construction:
given an output configuration, the switching sites, and some small
side information (which we call a "code"), we can reconstruct the
input.
Lemma 6.6 (Inverse codes and contact probabilities). Fix the output
fields, x, z, the old-map seeds, and the priority orderings. A
valid switching input can be specified by
- the sequence of selected indices i, and
- the "gaps" locating the chosen seams in the ordered list of
bridges separating z from x,
without using the fresh contact uniform variables.
After integrating over those fresh uniforms, the total mass of valid
codes is at most
W^k, where
W = 1 + sum_{l=1}^{M} min{1, 2 M^s / l} <= C M^s log M.
Sketch. The reconstruction: from the code, reconstruct the sequence
of seams and pieces. Undo the exchanges in reverse order. This
recovers the input fields. Then replay the old-map chain from z and
check that all successes and endpoint constraints hold.
For the mass bound: the "gap" l_i at the i-th seam is at most
|B_i| <= M (the size of the piece). The contact probability for
choosing the actual edge is at most K_i / (number of bridges already
accounted for). Standard harmonic bound: min{1, 2 M^s / l}. Summing
over the possible l in [1, M] gives W. Raising to the k-th power
because there are k seams.
The log factor M^s log M appears because sum_{l=1}^{M} 1/l ~ log M.
6.6 Mean load.
Let D' be a fixed reference iid distinguished field. Define the
"load" L_x(z, D') on outputs z: essentially, the total probability
mass of valid inverses divided by n.
Lemma 6.7 (Mean load). Let F(x, z) = E L_x(z, D'). Then
F(x, z) = (u^k / n) sum_{y in O}
P_{p_c}(y in C_x, n <= s_x < 2n) K^k(z, y),
c pi u^k <= b_0 := sum_{z in O} F(x, z) <= C pi u^k,
|| F / b_0 ||_{2->2} <= r^k.
Proof sketch. The first display is a mass-transport calculation: the
density comparison between the switched experiment and the reference
experiment preserves total mass, and the k independent old steps
contribute exactly u^k times the k-fold endpoint kernel K^k.
The second line just bounds F's row sum by the height of the bin
(scales n to 2n). The third line: F/b_0 is B_n K^{k*}, where B_n is
the iid distinguished density of y in C_x at scale n; B_n / (its row
sum) is a stochastic kernel so has norm <= 1, and K^{k*} also has
norm r^k.
6.7 Second moment of the load.
Lemma 6.8 (Second moment of the load). There is a fixed polynomial
Q(k, M) >= 1 such that, whenever kM <= n/2 and n >= (W/u)^k,
E L^2 <= Q(k, M) pi u^{2k}.
This is the technical heart. The bound is what stops the load from
concentrating on rare fields.
Sketch. Write v = kM. Expand L^2 by using the same reference
distinguished field D' and two independent auxiliary fields + seeds
for the two summands. Classify summands into three types:
Type 1: at least one inverse makes no switch. Then the endpoint
of the second inverse lands inside the reference root cluster.
BK + row/column sums bound the contribution by 4 u^k b_0 <=
C pi u^{2k}.
Type 2: hanging components B^1, B^2 are nested or graph-adjacent.
Each such pair contributes at most W^k. The number of pairs is
bounded by N_v = v + v^2 + d v^3 (choices for the second endpoint
given the first hanging component). Summing gives
2 b_0 N_v W^k / n <= C N_v pi u^{2k}.
Type 3: hanging components are disjoint and graph-nonadjacent.
Here the two inverses act on disjoint edge sets and can be undone
independently. The joint undo is INJECTIVE without needing any
code, so the mass is bounded by n^{-2} times the reference
experiment's mass. Retaining only the "both chains succeeded and
hit the reference cluster" event gives something of order
v^2 u^{2k} pi.
Combining, and taking Q(k, M) a large multiple of N_v, gives the
lemma.
6.8 One amplification step.
Lemma 6.9 (One amplification step). Fix an old map. For n in N
going to infinity and k = O(log n) with kM <= n/2 and n >= (W/u)^k,
there is, for all sufficiently large such n, a new local map with
u' >= c' pi / Q(k, M),
r' <= 2 r^k,
M' = 2n + kM.
The threshold for n may depend on the old map.
Proof sketch. Set b = C_0 Q(k, M) u^k for a big constant C_0. By
Lemma 6.7 and Lemma 6.8, discarding fields on which L > b loses
mean mass at most
E[L; L > b] <= E[L^2] / b <= b_0 / 4.
Then also discard fields where the root cluster is not good for
cap M'; by Proposition 5.1 this loses probability at most
b exp(-(M')^eps). Since (M')^eps -> infinity and everything is
polynomial, this is at most b_0/4 for large n.
On a retained field output z with probability L / b, else fail.
This is a legit rule because L <= b on retained fields.
The new row sum is b'_0 >= b_0 / 2. The new conditional kernel F'/b'_0
is dominated by F/b_0 in absolute value, so its norm is at most
2 r^k. The new success probability is b'_0 / b >= c' pi / Q(k, M).
The physical map is covariant and local: it processes only finitely
many bits around x.
6.9 Iteration.
Proof of Proposition 6.3.
Choose xi > 0 such that
c_xi := (beta + xi + (s + xi)(1 + xi)) / (1 - xi) < 1.
This is possible because beta + s < 1 and we can shrink xi.
Start with the map of Lemma 6.4, with H > 1 and M large. For a fixed
map, define
t = U + (s + xi) m,
a = ceil( C M^s log M / u ).
Choose C large enough that a >= max(2, W/u). For fixed old map and a,
choose n in N large, and set
k = floor( log n / log a ).
Then:
k -> infinity, k = O(log n), n >= a^k >= (W/u)^k,
kM <= n/2, and all goodness / truncation thresholds eventually hold.
Also
k log a <= log n < (k + 1) log a <= (k + 1) t.
By Lemma 6.9, the polynomial dependence of Q on k for fixed M, and
pi >= n^{-beta}, we can make n large enough that:
U' <= k (beta + xi) t,
m' <= k (1 + xi) t,
H' >= k (1 - xi) H > 1.
Therefore
t' := U' + (s + xi) m' <= c_xi * t,
H' >= (1 - xi) H.
So (t' / H') <= c_xi * (t / H), and c_xi < 1.
Also make H' bigger by choosing n larger if necessary (at each stage
choose n so that H' >= 2H). This changes none of the inequalities
above.
Iterate: (t_j / H_j) contracts geometrically to 0 while H_j -> inf.
Since U + m <= max(1, (s + xi)^{-1}) t (because U, m >= 0), this
proves (U + m)/H -> 0 as well.
Done: we have produced local endpoint maps whose figure of merit
(U + m)/H is arbitrarily small and whose H is arbitrarily large.
That is Proposition 6.3.
==================================================================
7. CRITICAL MOMENTS OF THE CLUSTER SIZE
==================================================================
7.1 What we are proving.
This section converts the local endpoint maps of Section 6 into a
contradiction with hypothesis (6.1). The conclusion will be:
Proposition 7.1 (Critical fractional moments). For every
alpha in (0, 1/2),
sup_x E_{p_c} s_x^alpha < infinity.
In other words, at criticality, every fractional moment strictly below
1/2 is finite. This directly contradicts our assumption (6.1).
7.2 Strategy.
Take a map from Proposition 6.3, with H enormous and (U+m)/H tiny.
Run it at p slightly less than p_c. Its endpoint kernel has tiny
norm K_p. Iterate it many times. Because the norm is tiny, the
j-fold iterated endpoint mass must exit any fixed set very rapidly.
In particular, if you set up the root cluster of x as such a set, a
lot of the j-fold iterated mass lands outside it. Comparing to
"how much mass stays inside" gives a lower bound on the amount of
fresh-cluster mass that the map reaches outside.
That lower bound turns into a lower bound on the derivative of chi.
Integrating gives an upper bound on chi near criticality. That upper
bound then conflicts with the assumed singular behaviour at alpha.
7.3 Setting.
Fix a map from Proposition 6.3 with cap M and success probability u.
Pick an interval [p_0, p_c) on which the map's parameters (u_p, K_p)
are close to their critical values:
u_p >= u/2,
||K_p|| <= e^{-(H-1)} < 1.
This holds by continuity of the map's statistics near p_c, and by
picking p_0 >= p_c / 2.
Notation. For a domain D and a vertex v in D:
f_D(v) = E_p |C_v^D| (cluster size in D),
f_D(v) = 0 (for v not in D).
We will use two auxiliary quantities:
chi(p) = [ E_p |C_o| ] (susceptibility, averaged over types),
chi_0^+ = sup_x E_p |C_x| (max susceptibility).
7.4 A key estimate about maximal susceptibilities in an intrinsic
ball.
Lemma 7.2 (Maximal susceptibility in a ball). For a finite
deterministic domain D, let B^D(v, M) be the set of vertices reachable
from v by an open path of length at most M inside D. Then for every
v in D and p in (0, p_c):
E_p max_{z in B^D(v, M)} f_D(z)
<= (1 + (1-p)M/p) f_D(v).
In words: the expected maximum of the susceptibility over a small
intrinsic ball is at most a constant times the susceptibility at v,
and the constant is 1 + O(M).
Proof sketch. On a finite D, pick the maximizer Z by a fixed tie
rule. For a fixed w, expose the cluster B = C_w. Replace all edge
bits incident to B by fresh ones (a cost of at most 1 jump per edge).
This doesn't change the law of the maximizer Z (fresh bits preserve
product law), so a bit of algebra gives an identity:
sum_{w in D} P( Z in B_w ) = E max_{z in B^D(v, M)} f_D(z).
Now bound P(Z in B_w) for each w. Two cases: v in B_w (rare,
controlled by the fact that w is the maximizer and v is close to a
maximizer), or v outside B_w. In the second case, along a short open
path from v to Z, one edge must have been closed in the original
configuration and open after the fresh replacement. Pivotal edges
of this form are "among the first M bridges" separating v from w,
contributing at most (1-p)/p * M * T_p(v, w). Sum over w.
The intuition: you can move a root within the M-ball and pay only
M times the price. This is used to control the split between
"endpoint landed in the root cluster" and "endpoint landed outside".
7.5 The map acting on susceptibilities.
Lemma 7.3 (The map in a deleted domain). Fix a map with parameters
u, M, H as in 7.3. For a deterministic set A, define
F_A(v) = f_{V \ A}(v) / chi for v not in A,
F_A(v) = 0 for v in A,
h_A(v) = sum_{a in A, dist(v, a) <= M} sum_{b ~ a} F_A(b).
Then there are constants Z, C_map (uniform on [p_0, p_c)) with
2 <= Z <= C M/u and
(K_p F_A)(v) <= Z F_A(v) + C_map h_A(v). (7.4)
In words: applying the map to a susceptibility function pays "Z
times the value at v" inside the domain, plus a correction for the
"deleted" set A that is captured by the h_A function.
Proof sketch. Unconditionally, the map's endpoint y is connected to v
by an open path of length at most M. If that path avoids A, y is
inside the M-ball of v in V \ A, so Lemma 7.2 applies. If the path
exits A on its way to y, let a ~ b be the last exit from A, and use
Harris with the event "the segment from b to y is open" to transfer
susceptibility from y back to b. The transfer cost is p^{-M}, and
the extra factor of u_p^{-1} accounts for the map's success
probability.
The coefficient Z = (1 + (1-p)M/p) / u_p is the constant from
Lemma 7.2 with the success-probability division. Its lower bound
Z >= 2 comes from M >= 1 and u_p <= 1.
7.6 Iterating the map.
The point of (7.4) is that iterating the map j times, and averaging
over a random root cluster A, gives an upper bound on how much of
the iterated mass stays near the root:
E_hat (K_p^j F_A)(x) <= C_map Z^j D(p) (7.5)
where E_hat is the "root-sized" average (details in a moment) and
D(p) = chi^{-2} sum_{b ~ o} E_p(s_o s_b; C_o != C_b) is a specific
quantity tied to the derivative of chi.
7.7 The derivative of susceptibility.
A classical identity (the "Russo formula for chi") says:
(1-p) chi'(p) = chi^2 D(p).
Why? Differentiate chi = sum_y T_p(o, y). The derivative of each
connection probability T_p(x, y) equals the probability that the
"final" pivotal edge (the one whose open/closed status controls the
connection) is open, times a factor (1-p)^{-1}. Summing over that
edge and reshaping gives the displayed identity.
The consequence we need: if D(p) is uniformly bounded below by
c_gamma chi^{-gamma} near p_c, then chi'(p) >= c chi^{2-gamma},
i.e., chi has a strong lower growth rate near criticality. That
is the key estimate that we are now about to prove.
7.8 Lower bound on D(p).
Given the map with small norm r = e^{-H}, we can show D(p) must be
large (i.e., chi^{-gamma}). Here is the mechanism.
Setup. Take the root cluster A = C_x in an independent p-field.
Use the "root-sized measure" E_hat[G(A)] = E_p[(s_x / chi) G(C_x)].
Lower bound. On the event where the root cluster touches a specific
edge (say a specific edge from a to b), the exterior cluster of b is
fresh and its contribution to F_A(b) has a size comparable to
T_p(a, b) chi^{-1}. Doing this uniformly over a and summing over
edges crossing from A gives:
E_hat h_A(x) <= C_map D(p). (7.6)
Iterating 7.4 and using the row sum of K_p:
E_hat (K_p^j F_A)(x) <= C_map Z^j D(p). (7.7)
This is an upper bound on what the map can do across the boundary.
Another lower bound. On the other hand, if we could freely apply
K_p^j without the "A-removal correction", the iterates would produce
a full chi of mass. Each "leak" past the boundary corresponds to
externalising one unit. Because K_p has tiny norm r < 1:
E_hat (K_p^j F_A)(x)
= (mass that stayed in D \ A after j steps)
+ (mass that leaked out through A).
The first term is at least c_0 > 0 uniformly for large j (a lower
bound coming from Harris and the fact that a small ball around x is
almost as likely to succeed now as at p_c). The second term is
identifiable exactly via mass transport:
excluded mass <= ||K_p||^j E_p s_x^2 / chi^3 (7.8)
which shrinks like r^j.
Choose j = ceil( log(C_* chi) / (H-1) ) so that r^j chi^3 is at most
(c_0/2) chi^3 / chi^3 = c_0/2. Then the upper (7.7) and the lower
(c_0 minus the small term) bounds sandwich D(p).
Result (the inequality at the heart of the proof):
D(p) >= c_map chi^{-(U+m+C')/(H-1)}. (7.9)
Because (U+m)/H -> 0, we can arrange (U+m+C')/(H-1) <= gamma for any
fixed gamma > 0. Combined with (1-p) chi' = chi^2 D(p), this gives
(1-p) chi'(p) >= c chi^{2 - gamma}. (7.10)
7.9 Integrating.
Integrate (7.10) from p < p_c to p_c. Let Gamma = 1 - gamma.
Rewrite as
d/dp chi^{-Gamma} <= -Gamma c (1-p)^{-1}.
Since 1-p stays bounded near p_c, integrating yields
chi^{-Gamma}(p_c-) - chi^{-Gamma}(p) <= -c (p_c - p).
Because the left side is at most itself and chi^{-Gamma} >= 0, we
get
chi(p) <= C_gamma (p_c - p)^{-1/Gamma}. (7.11)
Since gamma > 0 is arbitrary and Gamma = 1 - gamma -> 1 as gamma -> 0,
we can make Gamma as close to 1 as we like; hence chi grows at most
like (p_c - p)^{-(1 + something small)}.
7.10 From susceptibility to critical tails.
The last step, the transfer from a subcritical susceptibility bound to
a critical cluster-size tail, is a fairly standard "two-point
exploration comparison". Fix a large integer N. Set
p = p_c - N^{-1/2}.
Explore from x until the cluster is exhausted or N vertices discovered.
Use a fixed non-repeating query order. There are at most dN queries.
The transcript decides the event {s_x >= N}.
Let L_N be the likelihood ratio of the transcript's law at p_c
relative to its law at p. Because each query is a fresh Bernoulli bit,
its b-th moment factor near p is controlled:
p(p_c/p)^b + (1-p)((1-p_c)/(1-p))^b <= 1 + C_b / N^2.
(Here p_c - p = N^{-1/2} so (p_c - p)^2 = 1/N.) For dN queries,
successive conditioning gives
E_p L_N^b <= (1 + C_b/N)^{dN} <= e^{d C_b}.
The last estimate is independent of N.
Hölder's inequality + Markov: for any b > 1,
P_{p_c}(s_x >= N)
= E_p [ L_N 1_{s_x >= N} ]
<= C_b' ( chi(p) / N )^{1 - 1/b}.
Plugging in chi(p) <= C (N^{-1/2})^{-(1+gamma)} (from (7.11) at
gamma small and N large enough), we get
P_{p_c}(s_x >= N)
<= C_b'' N^{-(1 - 1/b)(1/2 - gamma/(2(1-gamma)))}.
For b large and gamma small enough that 1/2 - gamma/(2(1-gamma)) >
alpha (possible because 0 < alpha < 1/2), the exponent theta > alpha. Then
E_{p_c}[s_x^alpha]
= sum_{N >= 1} ( (N+1)^{alpha} - N^{alpha} )
P_{p_c}(s_x > N)
<= C sum_{N >= 1} N^{alpha - 1} N^{-theta} < infty.
This contradicts (6.1). That proves Proposition 7.1.
7.11 From critical tails to a susceptibility bound.
We also need the complementary direction: given
sup_x E_{p_c} s_x^alpha < infty for some alpha in (0, 1/2),
prove
chi_max(p) <= C_eta (p_c - p)^{-1 - eta}
for every eta > 0. (7.12)
This is Proposition 7.4. It is an adaptation of a decision-tree
covariance bound (due to O'Donnell-Saks-Schramm-Servedio) to the
quasi-transitive setting.
Setup: In a finite domain, fix x and n >= 2, let f = 1_{s_x >= n},
mark vertices independently with probability 1/n, let g = 1_{C_x
contains a mark}. The mark-based algorithm to decide g first reveals
all marks, then explores cluster-by-cluster.
Each edge is queried with probability at most
2 C_a n^{-a}, where a in (0, 1/2) (from the moment bound
and Harris).
The decision-tree covariance inequality says:
Cov(f, g) <= sum_e (reveal prob of e) * (influence of e on f).
But influence of e is exactly 2 p (1-p) times P(e is pivotal to f), so
finite-product differentiation gives
Cov(f, g) <= C_a n^{-a} * 2 p(1-p) * d/dp P_p(s_x >= n).
Combining with a lower bound on Cov(f, g) from conditioning on the
graph itself:
Cov(f, g) >= ( 1 - (1 - 1/n)^n - C_a n^{-a} ) P_p(s_x >= n)
>= c P_p(s_x >= n) (for large n).
This forces:
d/dp P_p(s_x >= n) >= c_a n^a P_p(s_x >= n) (7.13)
for p in (0, p_c]. Multiplying by exp(-c_a n^a p) shows that
exp(-c_a n^a p) P_p(s_x >= n) is nondecreasing in p. Evaluating
at p_c gives the explicit stretched-exponential tail:
P_p(s_x >= n) <= C_a n^{-a} exp( -c_a (p_c - p) n^a ). (7.14)
Now sum over n. A substitution t = c_a (p_c - p) n^a makes the sum a
Beta-function integral:
sum_{n >= 1} n^{-a} exp( -c_a (p_c - p) n^a )
<= C_a (p_c - p)^{-(1-a)/a}.
With a = 1/(2 + eta), the exponent is (1 - a)/a = 1 + eta. That
gives (7.12).
7.12 Summary of Section 7.
- Critical clusters have all fractional moments below 1/2 finite.
- Subcritical susceptibility grows at most (p_c - p)^{-1 - eta}
for every eta > 0.
Both will be used repeatedly later (in the trace bound of Section 8
and in the corridor argument of Section 9).
==================================================================
8. THE TRIANGLE TRACE STAYS SUBPOWER
==================================================================
8.1 What we are proving.
For p < p_c, write
T = T_p, m_p = ||T_p||_{2->2}, a_j = tr(T^j),
where tr is the "type-averaged" trace from Section 2 (protected by
mass transport). The key quantity here is
a_3 = tr(T^3) = [ sum_v T_p(o, v)^3 ],
called the triangle trace (it is the type average of the triangle
diagram x -> v -> o -> x).
Proposition 8.1 (Subpower triangle growth). For every eta > 0 there
is C_eta < infinity such that
a_3(p) <= C_eta (p_c - p)^{-eta} for p_c / 2 <= p < p_c.
So the trace grows more slowly than any positive power of
(1/(p_c - p)). This is used in Section 9 to bound the "correction
term" of the corridor deformation.
8.2 Strategy.
The derivative of a_3 expands as a sum over "how many graph edges
cross between two terminal clusters", each edge weighted by a matrix
of connection probabilities. To bound the sum, we:
(i) Bound the contribution of pairs of *small* clusters directly
using the susceptibility bound (7.12).
(ii) Bound the contribution of pairs of *large* clusters using a
"contact tail" estimate (Lemma 8.3 below).
(iii) Interpolate via Cauchy-Schwarz.
The novelty is (ii): to bound contacts between two clusters at
criticality, compare two percolation explorations that start from
the two clusters and produce almost the same edge score. The
difference is exactly the number of contacts. Each exploration
concentrates by a Chernoff bound, so the difference between them
concentrates too.
8.3 The rerooting identity.
Define a functional on invariant functions of ordered pairs of
finite clusters:
D(F) = [ E_p (1/s_o) sum_{B != C_o} F(C_o, B) ].
For a nonnegative kernel J, write
k_J(A, B) = sum_{x in A} sum_{y in B} J(x, y).
If J = Adj (adjacency kernel), then k_Adj(A, B) = number of graph
edges between A and B (call this k_e).
Rerooting identity (from mass transport):
D( k_J F )
= [ E_p sum_v J(o, v) F(C_o, C_v) 1_{C_o != C_v} ]. (8.1)
Interpretation: D(k_J F) is the "expected k_J-weighted F, averaged
over roots and over the second cluster", and the right side
re-expresses it as a sum over pairs of vertices in different clusters,
with the pair weighted by J.
8.4 The contact tail.
Lemma 8.3 (Contacts of two large clusters). Fix any 0 < alpha < 1/2
and epsilon_1 > 0 small enough that
r := 1/2 + epsilon_1 - 2*alpha < 0.
Then, uniformly for p_c / 2 <= p < p_c and L >= 1,
D( k_e^2 * 1_{min(|A|, |B|) >= L} ) <= C L^r. (8.2)
So the square of the edge contact count between two large clusters,
averaged over roots, decays as a negative power of L. Since r < 0,
the right side -> 0 as L -> infty.
Proof idea. Fix an oriented graph edge (x, v) and a size bin
n <= min(|C_x|, |C_v|) < 2n. There are three ingredients.
(i) On the event C_x != C_v and n <= min sizes < 2n,
two fresh explorations (one in the full graph from v, one in
the induced graph after removing C_x) finish the same cluster,
so their edge scores differ by exactly p * k_e(C_x, C_v).
(ii) Each edge score is a sum of ~n fresh queries independent
centered Bernoulli(p) variables; by Hoeffding,
P( |score| > t ) <= 2 exp(-2t^2 / N).
With t = n^{1/2 + epsilon_1} this is super-polynomial small
for large n.
(iii) BK applied to disjoint witnesses bounds
P(C_x != C_v, both sized near n) <= C n^{-2*alpha}
(from the critical fractional moment bound of Section 7).
Combining: with high probability, k_e(C_x, C_v) is O(n^{1/2 + eps_1}),
and its BK-weighted contribution per bin is O(n^{1/2 + eps_1 - 2alpha}).
Summing over dyadic bins in L gives the bound.
8.5 The derivative of a_3.
Using the rerooting identity and the "differentiate by closed pivotal
edges" identity of Section 2, one shows that
(1-p) a_3'(p) = 3 D( k_e * k_J ), J = T^2, (8.3)
almost everywhere p < p_c. Interpretation: the trace's derivative
counts "how many edges separate two terminal clusters, weighted by
the probability mass of connections across J".
Bounding D(k_e k_J) is the task.
8.6 Splitting small and large.
Fix alpha in (0, 1/2). Split D(k_e k_J) according to whether
min(|A|, |B|) < L.
Small contribution. Use the susceptibility bound (7.12):
D(k_e k_J 1_{|A| < L}) <= d c_sigma a_3 * [E_p s_o 1_{s_o < L}]
<= C L^{1-alpha} a_3.
Large contribution. Apply Cauchy-Schwarz for the positive measure
underlying D:
D(k_e k_J 1_{min >= L}) <= D(k_e^2 1_{min >= L})^{1/2} *
D(k_J^2 1_{min >= L})^{1/2}.
The first factor is bounded by (8.2). For the second,
D(k_J^2) <= tr(J * T * J * T) = a_6 <= m_p^3 a_3.
Putting both together:
D(k_e k_J 1_{min >= L}) <= C L^{r/2} m_p^{3/2} a_3^{1/2},
where r = 1/2 + epsilon_1 - 2*alpha.
8.7 Combining.
Set b = sqrt(a_3). Then b >= 1 (since a_3 >= 1 by the diagonal
sum), and b is locally absolutely continuous by the same argument
used for chi. Combining (8.3) and the two bounds above:
b'(p) <= C L^{1-alpha} b
+ C L^{r/2} m_p^{3/2} (a.e.). (8.4)
Now choose the parameter L to optimize. We want b'(p) bounded by a
small power of delta = p_c - p. Pick
L = delta^{-(2 - zeta)} for 0 < zeta < min(1, eta),
and require
1 - alpha < 1 / (2 - zeta),
r/2 < -1 (i.e. r < -2),
and use the subpower bound m_p^{3/2} <= C delta^{-3/2 - eta'} for
small eta' > 0 (from (7.12)). With these choices, both terms on the
right of (8.4) are of size C times a small power of delta, and the
integral of the resulting first-order linear ODE converges to give
b(p) <= C_eta delta^{-eta/2}.
Squaring:
a_3(p) <= C_eta' delta^{-eta}.
That is the proposition. The parameter zeta was chosen small enough
to make A_* = (2 - zeta)(1 - alpha) < 1 and B_* =
(2 - zeta)(r/2 + ...) + (3/2)(1 + eta') < 1 + eta/2; both are
possible because at (alpha, eps_1, eta') = (0, 0, 0) the values
are (1 - zeta/2) and (1 + zeta/4) respectively.
8.8 Why the argument works.
The three ingredients we used were:
- the fractional-moment bound P_pc(s_x >= n) <= C n^{-2*alpha}
(from Section 7),
- the subpower susceptibility bound chi(p) <= C delta^{-1-eta}
(also from Section 7),
- and the fact that at criticality, the edge count between two
fresh explorations concentrates (a Chernoff bound applied to
the score difference).
None of these depends on amenability or the operator norm. The
trace bound is a "mean-field-like" estimate valid for any nonamenable
quasi-transitive graph.
==================================================================
9. CORRIDORS AND DEFORMATION
==================================================================
9.1 Why we need a new tool.
Suppose for a moment that we have:
- a subpower bound on chi(p) (Section 7), and
- a subpower bound on a_3(p) (Section 8).
Together these already imply that chi does not blow up too fast near p_c
and that the "triangle" stays controlled. But these alone do not rule
out ||T_{p_c}|| = infinity.
Why not? Because ||T_p|| can be huge even while chi is moderate. Being
huge in operator norm just means "T_p sends some vector f of norm 1 to
a vector of large norm" — and that vector can be chosen to exploit the
multiplicity of distant clusters, not the size of any one cluster. On
a nonamenable graph, this kind of exploitation is exactly what a
non-unique-percolation phase permits.
The fix: deform the connection kernel so that it penalises "cheap"
connections but does not touch "expensive" ones. The special
connections we penalise are called corridors.
9.2 Corridors.
A corridor is a simple open path gamma in G such that no vertex
strictly inside gamma has any other open edge incident to it.
In other words: the corridor is entirely fenced off. Its two
endpoints can connect to the outside world, but its interior is
hermetically sealed except for the path itself.
Why care? Because such corridors are exactly what force a
connection x <-> y to pass through a narrow bridge. If we could
penalise them, we would reduce the mass of connections that are
"only hanging on by a thread".
Formal construction. Fix p < p_c, integers k >= 3 and consider raw
paths w of k steps of the lazy walk P from a base u to an endpoint v.
Its "chronological loop erasure" is the simple path gamma_w obtained
by deleting loops from w in the order traversed. The interior of
gamma_w is denoted I_w, and ell_w is its length.
We retain a raw path w as a "template" iff ell_w >= 3 (so gamma_w has
an interior). Its blockers are all edges incident to I_w that are not
edges of gamma_w. Write b_w for the number of blockers. The
calibrating weight of the template w is
c(w) = mu_u(w) * p^{-ell_w} * (1-p)^{-b_w},
where mu_u(w) = product of transition probabilities along w.
The purpose of c(w): it compensates the "cost" of forcing gamma_w to
be open (a factor p^{ell_w}) and all its blockers to be closed (a
factor (1-p)^{b_w}). So c(w) * Prob(gamma_w open and all blockers
closed) recovers exactly mu_u(w), the un-conditioned raw-walk
probability. That is the calibration identity (Lemma 9.1 below).
9.3 Weighted connections.
For an induced domain D, a template w is eligible if gamma_w is wholly
contained in D. Define the weighted connection kernel
W_t^D(x, y) = 1_{x <-> y in D} * exp( -t * N_{xy}^D ),
where N_{xy}^D is the total weight, over all eligible templates
w whose gamma_w is open and pivotal for x <-> y inside D and whose
blockers are closed or absent, of the weights c(w).
The "pivotal for x <-> y inside D" condition means: every edge of
gamma_w is on every simple open x-y path in D. So gamma_w is a
required bridge.
Deformation parameter t >= 0. At t = 0 the kernel is just T_p, the
undecorated connection kernel. As t grows, the weight decays
exponentially in the "corridor burden" N_{xy}^D.
Final notation:
T_t(x, y) = E_p W_t^V(x, y), (the deformed kernel)
chi_t = [ s_t^V(o) ] (type-averaged susceptibility),
s_t^D(x) = E_p X_t^D(x) (weighted row sum),
X_t^D(x) = sum_y W_t^D(x, y),
m_t = || T_t ||_{2->2}.
The kernel is entrywise positive but bounded above by T_p. It is
invariant, symmetric, and monotone under edge-opening and under
domain-enlargement (a subtle but crucial point, see Lemma 9.2 below).
9.4 Basic properties.
Lemma 9.2 (Basic bounds and monotonicity).
There is a fixed C such that, with c_k = exp(C k),
(9.1) sum_{w : an edge e is in E(gamma_w)} c(w) <= c_k / k
for every edge e.
On a connection in a finite cluster,
(9.2) N_{xy}^D <= c_k * |C_x^D|.
For fixed t, W_t^D(x, y) is increasing under opening edges and
under enlarging the domain (using the same realisation).
The kernel T_t is invariant, symmetric, entrywise in [0, T_p], and
(9.3) m_t <= sup_x s_t^V(x) <= c_sigma chi_t.
t |-> T_t(x, y) and s_t^D(x) are continuously differentiable for
t >= 0, with a right derivative at zero.
Proof sketch.
(9.1): The total weight of templates using edge e is bounded by
summing mu_u(w) over all raw paths through e, which is at most
B^k * k/d for a constant B (from the p^{ell_w}, (1-p)^{b_w} factors).
Increase C if necessary.
(9.2): Every template counted for x <-> y uses edges on a simple
open x-y path (of which there are at most |C_x^D| - 1).
Monotonicity: Verify that a template counted after an edge open /
domain enlarged was already counted before. The pivotal and
blocker conditions are preserved.
Smoothness: Differentiating under the expectation gives
-N_{xy}^D W_t^D(x, y), which is dominated by c_k |C_x^D|^2 (finite
expectation, subcritical). Dominated convergence handles it.
9.5 Calibrating the deformation.
Lemma 9.1 (Corridor calibration). For a template w, let Q_w be the
event that gamma_w is open and all its blockers are closed in the
full graph. Then Q_w is independent of the percolation on
D_w = V \ I_w, and
(9.4) c(w) * Prob_p(Q_w) = mu_u(w).
Furthermore, on Q_w, the template is counted for x <-> y if and
only if the two exterior endpoints' clusters are distinct and the
terminals lie in opposite endpoint clusters of gamma_w.
In words: the corridor event isolates the "x" and "y" sides; the
template contributes only when they are genuinely separate.
9.6 Small change of operator norm.
Proposition 9.3 (Small change of operator norm). For every t >= 0,
(9.5) 0 <= T_0 - T_t <= 2 t * T_0 P^k T_0 (entrywise),
m_t >= m_0 - 2 t rho^k m_0^2.
The intuition: the deformation only penalises connections that use
a designated corridor. The derivative of T_t at t = 0 is
-N_{xy} W_t = -N_{xy} (at t = 0), and N_{xy} (the burden) is bounded
by the weight of corridors; summing gives at most 2 * (the kernel
T_0 P^k T_0 weighted one tap). The P^k factor is small (rho^k) on a
nonamenable graph because the lazy walk has spectral radius rho < 1.
Consequence: after t = t_* = (k R)^{C_2+2} / m_0, the norm m_t loses
at most O(B_* rho^k) << m_0, so m_t >= m_0 / 2 throughout the
deformation interval. The deformation hardly touches the operator
norm.
9.7 Decrease of the averaged susceptibility.
The other half of the argument: show that the deformation *does*
significantly decrease chi. That gives the contradiction (row sums
control the operator norm).
We need two lemmas.
Lemma 9.4 (Deletion estimate). For A subset D, let Nb[A] be A
together with all its neighbours in the full graph. For every v:
(9.6) s_t^{D \ A}(v) >= s_t^D(v)
- chi_0^+ * sum_{z in Nb[A]} T_0(v, z).
Idea: Verify that the only "loss" from deleting A comes from
simple paths that visit Nb[A]. Sum over those paths.
Lemma 9.5 (Two distinct exterior clusters). There is C' > 0 such
that for every induced domain D and u, v in D:
(9.7) E_p [ X_t^D(u) X_t^D(v) ; C_u^D != C_v^D ]
>= s_t^D(u) s_t^D(v)
- C' (chi_0^+)^2 T_0^3(u, v).
Idea: Expose the exact cluster A = C_u^D, including all its bits.
X_t^D(u) becomes deterministic on this event. For the second
terminal v not in A, the modified and original kernels agree
exactly (using the deletion estimate). Apply Lemma 9.4.
Lemma 9.6 (Decomposition into two legs). On Q_w, suppose x is in
C_u^{D_w}, y is in C_v^{D_w}, and these two clusters are distinct.
Then
(9.8) N_{xy}^V <= c_k + N_{xu}^{D_w} + N_{vy}^{D_w}.
Idea: Every template counted for x <-> y either uses gamma_w itself
(contributing at most c_k) or makes do with one of the two exterior
clusters (contributing to one of the legs).
Combining these three gives.
Proposition 9.7 (Decrease of the averaged susceptibility). For all
t >= 0,
(9.9) -chi_t' >= exp(-t c_k) * (
E_path [ 1_{ell_w >= 3}
s_t^{D_w}(u) s_t^{D_w}(v) ]
- C' (chi_0^+)^2 rho^k a_3 ).
The product term is set to zero for discarded raw paths (with
ell_w < 3).
Interpretation: differentiating -chi_t' pulls down an N_{xy} factor;
decomposing over templates; using the calibration (Lemma 9.1) and
the two-distinct-clusters estimate (Lemma 9.5); the result is the
product of the two exterior susceptibilities at the two endpoints
of the template, minus a small error controlled by rho^k a_3.
The "E_path" average is over auxiliary walks, not percolation; it
will be bounded below in Section 10.
9.8 The remaining gap.
We now have upper and lower bounds:
Norm: m_t >= (1/2) m_0 throughout [0, t_*]. (Section 9.6)
Row sums: chi_t decreases at rate at least
exp(-t c_k) * (E_path product) - small. (Section 9.7)
The product E_path[s_t^{D_w}(u) s_t^{D_w}(v)] is what the row sums
actually *are*, averaged over the chosen template. The only way to
make the row sum decrease is for the template-average to be large.
Section 10 supplies: a positive proportion b_* > 0 of raw paths have
both endpoint potentials large (specifically, s_t^{D_w}(u) and
s_t^{D_w}(v) are within a small factor of the full chi_t). This
converts the row-sum decrease into a concrete differential
inequality.
9.9 Path comparison along an edge.
We close the section with one more auxiliary lemma.
Lemma 9.8 (Comparison along a path). If a simple path in D joins b
to z and has length l, then
(9.10) s_t^D(b) >= exp(-t l c_k) p^l s_t^D(z).
Idea: On the event that the fixed path is open, every template
counted for z <-> y extends to a template counted for b <-> y with
an overhead of at most l c_k in the weight. Harris with the path-open
event gives the p^l factor.
This is used in Section 10 to transfer "large potential" from the
corridor endpoint where the potential is naturally measured, to the
escape endpoint where we need it.
==================================================================
10. FINDING PATHS WITH ESCAPES AT BOTH ENDS
==================================================================
10.1 What we need.
Section 9 left us with the differential inequality
-chi_t' >= exp(-t c_k) * E_path [ 1_{ell_w >= 3}
s_t^{D_w}(u) s_t^{D_w}(v) ]
- small error. (10.1)
To turn this into a real decrease, we need to know: there are plenty
of raw paths w whose two endpoint potentials s_t^{D_w}(u) and
s_t^{D_w}(v) are both substantial (comparable to the full chi_t).
That is the subject of this section.
10.2 The key selection lemma.
Lemma 10.1 (Two endpoint escapes). For every tau > 0 there are
constants
J in N, C_1 > 0, k_0 in N, b_* > 0,
depending only on G and tau, such that for every p_c/2 <= p < p_c,
every k >= k_0, and every R >= 1, a set of raw paths of
E_path-probability at least b_* satisfies all of the following:
(a) Its chronological loop erasure has length at least three.
(b) From each of its endpoints u, v, there is a simple path in
D_w (i.e. in the graph with the corridor interior removed)
of length at most
j = J + ceil( C_1 log((k+1) R) ) (10.2)
to a vertex z whose weighted (deformed) potential is large
in the following sense:
sum_{b in Nb[I_w]} T_0(z, b) <= tau / R. (10.3)
The constant b_* is fixed in advance, before p, k, R are chosen.
So: a positive fraction of raw paths have positive escape from both
sides. The escape length is logarithmic in R, and the escaped
vertex has tiny interaction with the corridor interior.
The rest of the section constructs this set.
10.3 Anchored segments.
Pick a geodesic segment gamma = (gamma_{-J}, ..., gamma_J) in G.
Such a segment exists (with length 2J) because G is infinite and
connected, so has infinite diameter. Write S = Gamma * gamma for
its orbit under Aut(G) (a set of anchored segments). Write O_i =
Gamma * gamma_i for the orbit of position i and vartheta_i for its
root weight.
For x in O_i, define
N_i = # { g in S : g_i = x }.
This is finite and positive because every anchored segment is
contained in a finite ball around any of its anchors. Because of
automorphisms, N_i is independent of the choice of x in O_i.
Construction of a "labeled" path.
Fix u in O_0.
1. Sample g uniformly among segments with g_0 = u.
2. Follow g's positive half from u to g_J.
3. Run a "middle" P-walk eta of length L = k - 2 J,
conditioned so that eta_L lies in O_J. (The conditioning
probability q_L = P^L(a, O_J) for a in O_J is bounded below
by c_* > 0, with c_* depending only on G.)
4. Given eta, sample h uniformly among segments with
h_J = eta_L.
5. Follow (h_J, h_{J-1}, ..., h_0) to v = h_0.
6. The resulting raw path w has length k.
Independently, after these choices, we run two further ordinary
P-walks alpha and beta of a common length m from g_{-J} and h_{-J}.
These are the two candidate escapes, of length J + m.
Let Q_u be the probability law of the full labeled object
xi = (g, eta, h, alpha, beta). If mu(zeta) is the product of
transition probabilities along any walk zeta, then
Q_u(xi) = mu(eta) mu(alpha) mu(beta) / (N_0 N_J q_L). (10.4)
This formula is used for the bijection / reversal arguments below.
10.4 Reversal.
The labeled experiment admits a rooted reversal:
xi^dagger = (h, reversed_eta, g, beta, alpha),
rooted at v. Symmetry of P gives
Q_u(xi) = Q_v(xi^dagger). by (10.4).
Note: the escape tails are *swapped*, not reversed. This is the
precise form of "rooted reversibility" needed here; we do not need
chronological loop erasure to commute with path reversal.
An immediate consequence: if F is an invariant function of xi,
then E_{Q_u} F = E_{Q_u} (F o dagger). So an estimate for "how
bad the escape from u can be" gives an identical estimate for "how
bad the escape from v can be".
10.5 Domination by the ordinary walk law.
For a fixed raw path w, let n_g and n_h count the full segments
compatible with its first and last blocks. Summing all compatible
full segments, all escape tails, and using n_g <= N_0, n_h <= N_J:
Q_u(w) = (mu(eta) / q_L) * (n_g / N_0) * (n_h / N_J)
<= mu(eta) / c_*. (10.5)
The ordinary walk probability is mu_u(w) = (2d)^{-2J} mu(eta).
So
Q_u(w) <= D_J * mu_u(w), D_J = (2d)^{2J} / c_*. (10.6)
That is: any event with probability >= c_0 under Q_u has probability
at least c_0 / D_J under the ordinary walk law. This is the sense in
which the constructions "transfer" to raw paths.
10.6 Avoiding the raw path.
The escape from u has to avoid all vertices of the raw path w except
at u itself. We bound, uniformly in the escape-tail length m, how
likely that is.
Consider the escape from u. Its "negative half" (from g_{-J} up to
g_0 = u) plus the "positive half" of g's segment, plus the random
middle eta + escape tail alpha, all live in the graph. Collisions
happen when eta or alpha hits one of the 2J + 1 vertices of the
labelled segment gamma_a.
For a fixed vertex c of the segment:
P( eta at time r = c ) <= rho^r (near-critical decay)
P( alpha at time l = c ) <= rho^l
P( eta_r = alpha_l = c ) <= rho^{r+l}
The last one uses symmetry of P and decay.
Summing over the 2J + 1 segment vertices, over r >= J and l >= 0,
and over conditioning on eta_L:
P( collision with gamma_a ) <= E_J(c_*)^{-1} (10.7)
where
E_J = (2J+1) * (sum_{r>=J} rho^r + sum_{n>=2J} (n+1) rho^n) / c_*. (10.8)
E_J -> 0 as J -> infty. So most escapes avoid the segment for large J.
For collisions with the "last block" (the segment h plus the escape
from v that has to avoid it), a similar argument shows:
P( collision with last block ) <= F_J * rho^L. (10.9)
where F_J is polynomial in J and rho is the walk norm. The rho^L
factor is what makes the escape avoid the far-side anchored segment.
There is also a lower bound on dist(u, v): if the walk stays too close,
it can be included in the event whose probability we control. So for
large k0, with probability at least 3/4 both escapes avoid their
"other" blocks.
10.7 Testing the potentials.
We also need the escaped vertices (terminals Z_1, Z_2 of the two
escape tails) to have small "interaction with I_w":
sum_{b in Nb[I_w]} T_0(Z_i, b) <= tau / R. (10.10)
Before imposing avoidance, the two escape tails are independent
ordinary P-walks. Their terminal Z_i is thus smoothed: by
Schramm's lemma (Lemma 10.2 below),
(P^l T_0)(a, b) <= sqrt(c_sigma) * rho^l (10.11)
for every l >= 0. The size of Nb[I_w] is at most (d+1)(k+1). Hence
E [ sum_{b in Nb[I_w]} T_0(Z_i, b) | g, eta, h ]
<= C (k+1) * rho^m. (10.12)
Setting m = ceil( C_1 log((k+1) R) ), we get
P( potential bad for escape i ) <= 2 * tau^{-1} R (k+1) rho^m
<= 2 * tau^{-1} ((k+1) R)^{1 - lambda C_1}. (10.13)
For lambda C_1 > 1, this is small for all k >= k_0 and R >= 1.
So with probability at least 3/4 the potential test passes for each
escape.
Lemma 10.2 (Smoothing a connection kernel). For all a, b and
integers l >= 0:
(P^l T_0)(a, b) <= sqrt(c_sigma) * rho^l.
Why: positive-semidefinite Cauchy-Schwarz reduces (P^l T_0)(a, b)
to a diagonal entry of P^l T_0 P^l, which is bounded by
c_sigma * tr(P^l T_0 P^l) = c_sigma tr(P^{2l} T_0) <= c_sigma rho^{2l}.
10.8 Putting it together.
Choose J so large that 2 E_J <= 1/8 (avoidance of segment). Then
choose k_0 so large that (2 F_J + C_0) rho^{L_0} <= 1/8 (avoidance
of last block), and (10.13) <= 1/4 (potential tests) hold for all
k >= k_0 and R >= 1.
At the chosen parameters, all of the following hold simultaneously
with Q_u-probability at least 1/2:
- both escapes avoid the raw path (except at their starting
vertices),
- both escaped vertices satisfy the potential test (10.10),
- the raw path has loop-erased length at least 3 (because
dist(u, v) >= 3).
By (10.6), the same event has ordinary walk probability at least
(1/2) / D_J, hence at least b_* := vartheta_0 / (2 D_J) in the
type-averaged sense.
That proves Lemma 10.1. The constants J, C_1, k_0, b_* are all
fixed before p, k, R. This is the key quantifier-order property
needed for the final assembly.
==================================================================
11. THE FINAL CONTRADICTION
==================================================================
11.1 Setup.
We now have all the ingredients. Assume for contradiction that
||T_{p_c}||_{2->2} = infinity. (11.1)
We are going to derive a contradiction by considering the corridor
deformation at a carefully chosen parameter p < p_c, a well-chosen
corridor length k, and a well-chosen deformation time t_*.
Let p0 = p_c/2. For p0 <= p < p_c, define
delta = p_c - p, S = log(1/delta),
m_0 = ||T_p||, chi_0^+ = sup_x E_p |C_x|,
R = chi_0^+ / m_0 >= 1, a_3 = tr(T_p^3).
The R and a_3 quantities capture how "far" T_p is from being
"concentrated on a few directions".
11.2 Consequences of the assumed unboundedness.
Suppose (11.1). Using the sprinkling inequality (Section 3.4), if we
sprinkled at p with a = delta / (1-p) and this were bounded, then
T_{p_c} would be bounded too (contradiction). So a * d * m_0 >= 1,
which gives
m_0 >= (1 - p) / (d * delta). (11.2)
So ||T_p|| grows at least like 1/delta.
On the other hand, the subpower susceptibility bound (7.12) gives
chi_0^+ <= C_eta delta^{-1 - eta} for every eta > 0, (11.3)
and the subpower trace bound (Section 8) gives
a_3 <= C_eta delta^{-eta} for every eta > 0. (11.4)
Combining (11.2) and (11.3), the ratio
R = chi_0^+ / m_0 <= C_eta delta^{-eta} (11.5)
for every eta > 0. So R is *subpower*: log R = o(log(1/delta)).
Similarly log a_3 = o(log(1/delta)).
11.3 A useful comparison.
Claim (comparison of deformed row sums). There is a constant c_f > 0
such that, in the deformed kernel,
s_t^V(z) >= c_f chi_t for every z in V whenever t c_k <= 1.
Why. Connectivity plus finitely many vertex types means every vertex
is within bounded (L_f) distance of every vertex orbit. Apply the
path comparison (Lemma 9.8) from z to a maximum-s_{t}-orbit. The
cost is e^{-L_f} p0^{L_f}, uniformly over orbit representatives.
This is the key comparison that lets us lower-bound "how much
weighted connection mass exists at a randomly chosen vertex z" in
terms of the type-averaged chi_t.
11.4 Choose the deformation parameters.
Fix 0 < tau < c_f / (4 c_sigma), and let J, C_1, k_0, b_* be the
constants of the selection lemma (Lemma 10.1) for this tau. They
depend only on G and tau, and are now permanently fixed.
From the path-log estimate in Section 10, for large enough k,
p^{2j} >= c (k R)^{-C_2}, (11.6)
where
C_2 = 2 C_1 log(1/p0) and c = p0^{2(J+1)} 2^{-C_2}.
Now put
lambda = -log(rho) > 0, kappa = lambda K_* with
kappa > C_2 + 4,
A_delta = log(2 R) + log(2 + a_3) + log S,
k = ceil( K_* A_delta ), (11.7)
B_* = (k R)^{C_2 + 2},
t_* = B_* / m_0.
By (11.1) and (11.5), k -> infinity and k = o(S). Moreover, the
following three estimates hold (Section 11.6 for the derivation):
B_* rho^k = o(1), (11.8)
R^2 a_3 rho^k = o( (k R)^{-C_2} ), (11.9)
t_* j c_k = o(1). (11.10)
Let us see what they mean. (11.8): the corridor deformation is
"small" in operator norm (uses the spectral gap). (11.9): the
nonnegative error term in the propagation estimate is negligible
versus the "good" term. (11.10): the extra c_k factor from the
corridor decomposition stays under control over the whole
deformation time.
11.5 Two key preserved quantities.
In the deformation with parameters (p, k, t_*) on the time interval
[0, t_*]:
m_t >= m_0 * ( 1 - 2 B_* rho^k ) >= m_0 / 2 (11.11)
chi_t >= m_0 / ( 2 c_sigma ). (11.12)
The first uses Proposition 9.3. The second converts the row-sum
bound m_t <= c_sigma chi_t into a lower bound on chi_t.
11.6 The differential inequality.
Apply the "two endpoints" selection lemma (Lemma 10.1) to pick a
positive fraction of raw paths whose two endpoint potentials are
large. Specifically, for a selected path w with endpoints u, v:
s_t^{D_w}(z) >= c_f chi_t - chi_0^+ tau / R
= c_f chi_t - tau m_0
>= (c_f - 2 c_sigma tau) chi_t
>= (c_f / 2) chi_t, (11.13)
where the first inequality uses the deletion estimate (Lemma 9.4)
with the selection lemma's Nb[I_w]-control, the second uses
chi_0^+ = R m_0, and the third uses (11.12) and the smallness of tau.
Then apply the path comparison (Lemma 9.8) to the two escape paths
in D_w, each of length at most j. Their product is at least
s_t^{D_w}(u) s_t^{D_w}(v)
>= e^{-2 t j c_k} p^{2j}
* ( (c_f / 2) chi_t )^2. (11.14)
By (11.6) and (11.10), the right side is at least
c_1 (k R)^{-C_2} chi_t^2, (11.15)
uniformly on [0, t_*].
Such paths have E_path-probability at least b_*. So
E_path [ 1_{ell_w >= 3} s_t^{D_w}(u) s_t^{D_w}(v) ]
>= b_* c_1 (k R)^{-C_2} chi_t^2
=: c_1' (k R)^{-C_2} chi_t^2. (11.16)
On the other hand, the error term in Proposition 9.7 is at most
C' (chi_0^+)^2 rho^k a_3
= C' R^2 m_0^2 rho^k a_3
<= 4 C' c_sigma^2 R^2 rho^k a_3 * chi_t^2
= o( (k R)^{-C_2} chi_t^2 ), (11.17)
where the last inequality uses m_0 <= c_sigma chi_t (row sum bound)
and the little-o is the content of (11.9).
Therefore the differential inequality (9.9) becomes
-chi_t' >= (c_1' / 2) (k R)^{-C_2} chi_t^2. (11.18)
Let c_2 = c_1' / 2. Then over the interval [0, t_*]:
-chi_t' >= c_2 (k R)^{-C_2} chi_t^2. (11.19)
11.7 The closing argument.
Divide by chi_t^2 (which is positive) and rewrite as an ODE in
g_t = 1/chi_t:
d/dt (g_t) = -chi_t' / chi_t^2 >= c_2 (k R)^{-C_2}.
Integrate from 0 to t_*:
g_{t_*} >= g_0 + c_2 (k R)^{-C_2} t_*.
Since g_0 = 1/chi_0 > 0, this implies
1/chi_{t_*} >= c_2 (k R)^{-C_2} t_*. (11.20)
Now plug in t_* = B_* / m_0 = (k R)^{C_2 + 2} / m_0:
1/chi_{t_*} >= c_2 (k R)^{-C_2} (k R)^{C_2 + 2} / m_0
= c_2 (k R)^2 / m_0. (11.22)
That is, chi_{t_*} <= m_0 / (c_2 (k R)^2).
But (11.12) says chi_{t_*} >= m_0 / (2 c_sigma).
Combining:
m_0 / (2 c_sigma) <= chi_{t_*} <= m_0 / (c_2 (k R)^2).
Cancel m_0 and rearrange:
(k R)^2 <= 2 c_sigma / c_2.
But R = chi_0^+ / m_0 >= 1 by definition (row sum bound on T_0), and
k = ceil(K_* A_delta) where A_delta = log(2R) + log(2+a_3) + log S
-> infinity, and also k R -> infinity (because k -> infinity,
R >= 1). So (k R)^2 -> infinity, contradicting the bounded upper
bound.
That is the contradiction. Therefore (11.1) is false:
|| T_{p_c} ||_{2->2} < infinity.
This completes the proof of Theorem (critical boundedness).
11.8 Why the parameter choices work: the three estimates.
We promised (11.8)-(11.10). Here is how they follow.
From k = ceil(K_* A_delta) and A_delta >= log S, we have
rho^k <= ( 2R )^{-kappa} ( 2 + a_3 )^{-kappa} S^{-kappa}.
Since 2R, 2 + a_3, S are all >= 1 and k <= S (for large enough k,
using A_delta = O(log(1/delta)) and K_* fixed), we have
B_* rho^k <= C S^{C_2 + 2 - kappa} -> 0.
This is (11.8).
(k R)^{C_2} R^2 a_3 rho^k
<= C S^{C_2 - kappa} -> 0.
This is (11.9).
Finally,
log(t_* j c_k)
= - S + (C_2 + 2)(log k + log R) + log j + O(k)
= - S + o(S) -> -infinity.
So t_* j c_k -> 0. This is (11.10).
All three work uniformly over small delta because A_delta and k have
been chosen to grow slowly compared to S, and kappa is chosen larger
than C_2 + 4 to give the negative exponent.
11.9 The two remaining logical steps.
The proof above gives ||T_{p_c}|| < infinity (Section 11.7). From
that:
(i) Sprinkling (Section 3.4) at p = p_c with a small enough a > 0
gives boundedness of T_{p_c + delta}, hence p_c < p_{2->2}.
(ii) The forward inequality p_{2->2} <= p_u is proved in Section
2.5 as follows. If uniqueness holds at p, then for any
x, y there is a single infinite open cluster with positive
probability theta_x > 0. Harris gives T_p(x, y)
>= theta_x theta_y for all x, y. But then
<1_F, T_p 1_F> >= (min theta)^2 |F|^2, which grows like
|F|, so ||T_p|| = infinity: contradiction. So any p that
achieves uniqueness has unbounded T_p, hence p >= p_{2->2}.
Take infimum over such p.
Together, (i) and (ii) give p_c < p_{2->2} <= p_u.
That is Theorem (Hutchcroft's operator threshold).
==================================================================
12. CONSEQUENCES AND WHERE TO GO NEXT
==================================================================
12.1 Spinoffs of critical boundedness.
The main theorem says ||T_{p_c}|| < infinity. Once you have that, a
surprising chain of consequences opens up. They are known collectively
as "mean-field critical behaviour": the type of behaviour that
classically happens above the critical dimension (d > 6 for the usual
lattice), but which here is forced by the graph's symmetry and the
operator bound together.
The mechanism is the triangle condition. Recall
nabla_p(v) = sum_{y, z} T_p(v, y) T_p(y, z) T_p(z, v)
= < delta_v, T_p^3 delta_v >.
If T_p is bounded, this sum is finite:
nabla_p(v) <= ||T_p^3|| <= ||T_p||^3 < infinity.
So the triangle condition holds at p_c on the class of graphs in
the theorem. From that, a classical body of results (Aizenman-Newman
1984, Barsky-Aizenman 1991, and its quasi-transitive versions by
Hutchcroft) yields:
(a) Susceptibility exponent 1.
chi_x(p) ~ (p_c - p)^{-1} as p -> p_c from below.
(b) Percolation probability exponent 1.
theta_x(p) ~ (p - p_c) as p -> p_c from above.
(Here theta_x(p) = Prob_p(|C_x| = infinity).)
(c) Cluster-size tail exponent 1/2.
Prob_{p_c}(|C_x| >= n) ~ n^{-1/2} as n -> infinity.
(d) Intrinsic radius tail exponent 1.
Prob_{p_c}(rad_int(C_x) >= n) ~ n^{-1}.
(Intrinsic = measured along open paths.)
(e) Extrinsic radius tail exponent 1.
Prob_{p_c}(rad_ext(C_x) >= n) ~ n^{-1}.
(Extrinsic = measured in the graph.)
Here ~ means bounded above and below by positive constants times the
stated function. Constants can depend on the graph and on x; they do
not depend on p or n.
Reading the exponents: chi blowing up like 1/(p_c - p) is what you
would get on a regular tree. The cluster-size tail n^{-1/2} means
critical clusters are power-law distributed with exponent 1/2.
The radius tails n^{-1} mean that a critical cluster of radius n is
"rare like 1/n", which is less rare than a Gaussian-style tail would
predict.
The (d) and (e) statements require slightly more than the triangle
condition -- they use the strict inequality p_c < p_{2->2} to tap into
results of Hutchcroft (2020, 2022). The exact quasi-transitive
statements are in Hutchcroft 2022 ("Slightly supercritical percolation
on non-amenable graphs I").
12.2 Exponential connectivity between p_c and p_{2->2}.
Define pexp as the supremum of p such that
T_p(x, y) <= A e^{-a dist(x, y)}
for every x, y, with some A < infinity and a > 0 depending only on
G and p.
In other words, connection probabilities decay exponentially fast in
the graph distance. It seems natural that this should hold for small
p (deep subcritical) and finally fail well above p_c. The question is
where exactly.
Theorem (implied by p_{2->2} < p_u). For p_c <= p < p_{2->2},
T_p(x, y) <= 2 ||T_p||_{2->2}
* exp( - dist(x, y) / (e ||T_p||_{2->2}) ). (12.1)
So connection probabilities decay exponentially throughout
[p_c, p_{2->2}). In particular,
p_c < p_{2->2} <= pexp. (12.2)
That is: exponential connectivity persists strictly above criticality,
into the nonuniqueness phase, up to p_{2->2}.
The display (12.1) is proved as follows. Positive association gives
T_p(x, y) <= T_p(x, x)^{1/2} T_p(y, y)^{1/2} ||T_p||. Then a standard
lemma (Hutchcroft 2020, Section 2) extracts the exponential bound from
||T_p|| <= finite plus a power-series argument on the triangle
diagram. The exact prefactor e is not optimal but the exponential
rate 1/(e ||T_p||) is what Section 4.2 of the original paper reports.
12.3 Application to Cayley graphs.
Let Gamma be a finitely generated nonamenable group, S a finite
symmetric generating set (no identity). The Cayley graph Cay(Gamma, S)
has Gamma as vertex set and edges {x, xs} for x in Gamma and s in S.
Corollary 12.1. For every such (Gamma, S), the Cayley graph has
p_c < p_{2->2} <= p_u,
and all the mean-field exponents in 12.1 hold with constants depending
only on Gamma, S.
This is the original theorem applied to the transitive case. The
result does not require choosing generators: it holds for any fixed
S.
Earlier results (Pak-Smirnova-Nagnibeda 2000, Thom 2015) proved
pc < pu for *some* generating set. The upgrade here is "for every
generating set", and for the L^2 statement.
12.4 Multiple edges and loops.
The main theorem is stated for simple graphs. In the slight
generalization to allow loops and multiple edges, we first delete
loops (they never affect connectivity), then subdivide every remaining
edge (including each copy of a multiple edge) by inserting a new
vertex in the middle. This produces a simple graph H with:
- each old edge is now a 2-edge path,
- infinite clusters in H correspond bijectively to infinite
clusters in the original graph,
- the connection kernel of the original graph is exactly the
compression of the kernel of H to the old vertex set,
- p_c(G) = p_c(H)^2 and p_u(G) = p_u(H)^2,
- the operator thresholds satisfy p_{2->2}(G) = p_{2->2}(H)^2.
The compression / dilation step is what transfers both the operator
norm bound and the infinite-cluster count. Details are in Section
2.3 of the technical paper.
12.5 One curveball: the operator threshold can equal the uniqueness
threshold.
It is natural to ask: is p_{2->2} < p_u always, or can they be equal?
Hutchcroft and Pan (2024) show p_{2->2} = p_u for the Cartesian
product of a regular tree with an infinite amenable Cayley graph.
So the gap p_c < p_{2->2} proven here is compatible with p_{2->2}
being tight against p_u. This is the sharpest possible form the
"strict gap" can take in the operator language.
12.6 What this does *not* do.
- It does not give any quantitative control on the interval
(p_c, p_u). Its length may shrink to 0 in different graphs.
- It does not give an explicit p_{2->2} in terms of any other
invariant of G. Bounds depend on the graph and on the
operator itself.
- It does not extend to site percolation at this level of
generality. Site percolation is likely similar, but the required
mass-transport and pivoting arguments would need rework.
- It does not identify the "critical exponents" explicitly for
specific graphs; the mean-field exponent statements are "if
this class of graphs, then these exponents" independent of the
graph. For the regular tree, they coincide with the classical
computations; for hyperbolic groups, the exponents are also of
mean-field type.
==================================================================
13. GLOSSARY
==================================================================
This is the "read it once and come back to it" reference.
SYMBOLS
G, V, E graph, vertices, edges
x ~ y adjacency
deg(x) number of edges incident to x
Aut(G) group of graph automorphisms
O_x orbit of x under Aut(G)
h_V(G) vertex isoperimetric constant (inf of dA / A)
p_c(G) critical probability
p_u(G) uniqueness threshold
p_{2->2}(G) L^2 operator threshold
p_exp(G) exponential connectivity threshold
T_p(x, y) connection probability (x <-> y at p)
C_x open cluster of x (random)
s_x |C_x|
pi_n Prob_{p_c}(n <= s_o < 2n) (dyadic scale bin)
chi_x(p) E_p |C_x| (susceptibility)
chi(p) type average of chi_x
chi_max(p) sup_x chi_x(p)
a_j(p) tr(T_p^j), triangle (j=3), six-arm (j=6), ...
m_p ||T_p||_{2->2}
nable_p(v) sum_{y,z} T_p(v,y) T_p(y,z) T_p(z,v) (triangle diagram)
P lazy random walk kernel
rho ||P||_{2->2} (spectral radius; < 1 on nonamenable G)
CONCEPTS
amenability h_V(G) = 0
nonamenability h_V(G) > 0 (equivalently, exponential growth and rho < 1)
quasi-transitive finitely many vertex orbits
bond percolation each edge open independently with prob p
cluster connected open component
infinite cluster unbounded connected open component
pivotal edge a bridge whose toggling changes the event
good cluster finite cluster whose pivotal distances are controlled after
any vertex deletion (Section 5)
cap M bound on cluster size
local endpoint map randomized rule that either fails or outputs y in C_x
using finitely many bits; parameters (u, M, r)
figure of merit (U + m) / H, minimised in the amplification
corridor simple open path with no other open edges at its interior
deformation penalising corridors by exp(-t N_{xy})
escape path simple path from a corridor endpoint into the pulled-apart
graph with low interaction with the interior
anchored segment geodesic segment gamma of length 2J with well-defined
orbit / anchor structure
INEQUALITIES
Harris (FKG) E[fg] >= E[f] E[g] for increasing f, g
BK Prob(A [] B) <= Prob(A) Prob(B) for disjoint witnesses
three-arm bound Prob(x <-> y, x <-> z) <= sum_w T(x,w) T(w,y) T(w,z)
sprinkling T_{p + (1-p)a} <= sum_j a^j T_p (Adj T_p)^j
Russo derivative of connection probability = expected
number of closed pivotals
MAIN THEOREM
For any infinite connected locally finite quasi-transitive graph G
with h_V(G) > 0:
sup_{p < p_c} ||T_p||_{2->2} = ||T_{p_c}||_{2->2} < infinity,
p_c(G) < p_{2->2}(G) <= p_u(G).
Additionally, there exists p_c < p_1 < p_2 < 1 such that in a single
uniform coupling, almost surely for every p in [p_1, p_2] there are
infinitely many infinite open clusters.
KEY REFERENCES (for further reading)
Benjamini-Schramm 1996 -- posed the nonuniqueness conjecture
Haggstrom-Peres-Schonmann 1999 -- simultaneous phase theorem
BLPS 1999 -- critical finiteness for nonamenable Cayley graphs
Hutchcroft 2016 -- critical finiteness for quasi-transitive
exponential growth
Hutchcroft 2019 -- L^2 operator thresholds, nonunimodular case
Hutchcroft 2020a,b,c -- L^2 consequences, nonunimodular theorem,
exponential connectivity
Hutchcroft 2022 -- critical exponents, quasicritical tail
Aizenman-Newman 1984; Barsky-Aizenman 1991 -- triangle condition
consequences
Duminil-Copin-Tassion 2016 -- sharpness of phase transition
Antunovic-Veselic 2008 -- quasi-transitive subcritical decay
O'Donnell-Saks-Schramm-Servedio 2005 -- decision-tree covariance
Kozma 2011 -- finite modifications, pivotal trees
Aldous-Lyons 2007 -- unimodular random networks, finite trace
==================================================================
EPILOGUE
==================================================================
If you have made it all the way through, you have seen how a modern
mathematical theorem is built:
- A practical question (does percolation on nonamenable graphs
have a nonuniqueness phase?) is turned into an estimate on
an operator.
- The operator estimate is broken into sub-estimates, each of
which is smaller and more concrete than the last.
- Each sub-estimate is proved using a small toolkit of classical
inequalities (Harris, BK, Chernoff, Cauchy-Schwarz) plus one
or two clever ideas specific to the problem.
- Global arguments (differential inequalities in a "deformation
parameter") are used to string these together.
The reward is a statement about a very general class of graphs:
every nonamenable quasi-transitive graph satisfies p_c < p_u.
No tree structure, no planar embedding, no Gromov-hyperbolicity
needed. Just the abstract expansion property of the graph, and
a careful accumulation of small estimates.
This does not mean the subject is closed. Mean-field theory also
predicts quantitatively many things about critical percolation on
these graphs, most of which are still open for general
quasi-transitive nonamenable graphs. And the nonuniqueness
conjecture for site percolation is still open in this generality.
The methods here are a starting point, not a finish line.
For a reader who wants to continue:
1. Read Hutchcroft 2020 for the L^2 framework.
2. Read Duminil-Copin-Tassion 2016 for sharpness machinery.
3. Read the technical paper this file accompanies for exact
proofs of every lemma stated here.
4. Try to sharpen any one of the estimates in Section 11;
even small improvements are publishable.
Good luck.